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.