I believe a solution would look more like what Hal Finney called transparent servers [1]. This would be a way to solve the issue of scaling (and getting rid of mining oligarchs), but also dealing with the necessary privacy issues of contracts. Also DNS is not really a contract between 2 parties, but N parties, and there is a relationship between DNS and contracts (more on that per PM by request).