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.
There's a lower limit to the number of minutes between blocks. Below that, latency plays too big a factor. So you'd want to adjust the block reward and block size instead of the block frequency.
That would probably result in prices going too low, where there are more domain requests than the network is actually capable of fulfilling. Supply/demand can't be calculated automatically: there needs to be a market. If a separate chain is used, miners need to sell domain space. I'd just put the data in the Bitcoin chain and rely on Bitcoin's transaction fees, though.