What is the maximum number of names (domains) that can be registered with NameCoin? Is it 21,000,000 / 0.01 (the cost of naming) = 2.1B? 
from docs: "The name_firstupdate transaction has a network fee. The network fees represents namecoins (NC) that are destroyed. "

Am I missing something? If not, it seems like quite a small number.
Given increased use of Namecoin, which would lead to a shortage of namecoins as you describe, the fee would be reduced. I have previously seen plans to reduce the network fee to 0.001 or lower, but can not find it now.

These changes would require a hard fork of Namecoin, but it is important to note a fee is only destroyed upon a new registration. Updates of DNS records and domain renewal go to miners.

I am not aware of any hard block size limit, but should one exist (or be implemented with a hard fork) it would be unlikely to get anywhere near the 2.1 billion names as you describe.