As I said in the BitDNS discussion, hard-limiting the network-wide number of registrations will fail. If 50 domains are produced per block, then what happens when more than 50 domains are needed per 10 minutes? Prices will become uncompetitive and the system will lose popularity.
The point here is to validate ownership of names, not restrict the total number of names or in the system to an arbitrary upper limit, right?
If so, would it be possible to tie in the difficulty of the proof-of-work to be based on the number of new name requests seen in the past two weeks? That is, the more requests, the easier the difficulty of hashing a block, and the more quickly blocks are generated? POW would also obviously have to be tied into the amount of processing power being thrown at the network as well.