Clients only need to track the currently valid information (there is an expiry date for domains, for example) and not all applications need all of the data stored in the chain. So, much like Bitcoin itself, application specific versions of the information stored in the blockchain will be used by most applications and they can use SCIP or distributed trust models to check the validity of information instead of storing the entire blockchain locally.
For shits and giggles, I downloaded the top 1 million domains and some IP blacklists, resulting in a 4MB CSV file containing 142,202 IP <-> domain pairs. Simple Zip compression yielded 2:1 - 3:1 compression rates while PAQ8 delivered rates >4:1. A custom data-structure would likely yield even higher compression ratios.
Simple extrapolation of these numbers shows that 5megs can easily handle half a million such pairings. If traffic is distributed in a Zipf-like distribution, the .bit namespace can grow to 2.5 million domains (the size the .bi*z* domain space) and clients could still store the top 20% of sites which receive 80% of all traffic in a 5 meg cache. With even .INFO carrying 6 million domains, we have room to grow :)
And, finally, storage tends to get cheaper over time and the chain could be setup to dynamically set prices.