Actually I think that a Bitcoin-style approach would be better.

Basically just use something like Bitcoin's block chain, but store domain registrations instead of only transactions.

So you only get a domain if you can prove that you've send some computational power of your computer. In addition, once you've registered a domain and the registration is sufficiently far in the past, it is infeasible for an attacker to manipulate your domain due to the block chain (and the computational power required to attack or delete it).