It seems like killing two birds with one stone isnt enough on the bitcoin forum; one has to kill three.
Firstly, I would like to commend nanotube's+theymos proposal. I like it because it makes economic sense, and it is simple.
The design that I am proposing in this post is backwards compatible with nanotube's+theymos proposal, however solves all the issues said. (I still think there is really nothing wrong about how it is proposed to work as it is. However, if there is a better way of doing it, why not?)
Before we start, one must state that domain names a fundamentally different to currency, as they obtain their value in a very different manner; currency obtains values from being something that has restricted supply. Domain names, rather have values from the quality of the name, i.e. a short dictionary word has more value that a long random sequence.
If a restriction of the total number of domain names is made, it would be an arbitrary restriction, causing a lower efficiency market, thus reducing the attractiveness of using that market.
So with this in mind, lets design a system that can have an unlimited number of domain names; providing people are willing to pay for the service of claiming the domain name.
The main concern on the forum is the inclusion of other data in the block chain; the problem isnt a fundamental one, as the bitcoin transactions block chain is indeed data in its own right.
In discussions elsewhere, it has been shown that:
1. Generators will happily include any data that is profitable to include.
2. The block size will grow to a size that balances data demands and the profitably of the miners.
3. Clients only need to keep data that they interested in. Data that is irrelevant to the client may be forgotten once processed.
4. Transaction balances may be used to cull the chain of old transactions.
Therefore it has already been shown that the amount of data in the chain is not an issue with: generation (they get paid for it), or storage (they only keep what they want). The only outstanding issue is: transfers.
What has been discussed is that every client must download the entire block chain (before it is culled) then, every new block generated and check it. Only after processing may a client delete any data that it doesnt want. This accounts for a small amount of work while the chain is small, however the fear is when large amounts of irrelevant data (to any particular client) is included in the chain this task will become overly taxing.
I propose, a design hinted at by Satoshi, to solve this problem: Split bitcoin transactions into multiple groups.
While keeping the important tie between data and bitcoin transactions, (every bit of data still must include its compensation to the miners as a bitcoin transaction fee).
Group the transactions by templates. For example: Put the vanilla template bitcoin transactions into the vanilla group, the bitdns template bitcoin transactions into the bitdns group, the bitpgp template bitcoin transactions into the bitpgp group, and so on.
Finally include a summary group that contains only the changes to the transaction balances accumulated in all the other groups.
A Block could contain something like this:

Once one block has confirmed the previous block (checking that all the accounting is correct in the summary block), only downloading the merkle tree and the summary group is required to keep up2date about the changes. This is in-effect less data than is required to download now! If the client decides that it needs some in-particular bit of data from one of the other groups after checking the summary, it can optionally download that also.
The important thing to notice is it that there is no free lunch, every bit of data must still include the appropriate transaction fees, in bitcoins.
Nanotube and Teymoss design fits very nicely on top of this design, as the transactions that the BitDNS system makes will simply be automatically grouped by the template that the generators use to check the BitDNS transactions before accepting them. Allowing clients to download the BitDNS data if they want it, or just download the transaction summaries.