User:Gmaxwell/namecoin that sucks less
First, start with a committed UTXO set— I originally proposed[1] commited UTXO for namecoin use. This can be used to make lite resolvers which get provable strong results.
Next, degrade the security model to SPV— simplified payment verification (see the Bitcoin whitepaper) for the past history: Unlikely a currency, naming doesn't really require strong evidence that in the past the name authorities weren't cheating (inflating names? who gives a ?!#@). On syncup a node would grab headers, then pull the (say) last month of blocks and the UTXO from a month ago then apply forward and only check the recent updates. The old history wouldn't be validated, instead nodes would just trust the network it can reach.
Transaction data (but not live registrations) older than a month or so would be deleted forever.
Next, any kind of to-address of internal capacity tokens must be P2SH with a two layer hash like hash160. When you pay to an address you must also provide with the transaction (but external to it) the interior hash value (this would be the real address). Thus its not possible to store arbitrary data in payment addresses. (this is called P2SH^2. Alternatively, I later came up with a scheme using pairing cryptography that allows you to have a value which is provably a hash)
Next Key=value data must always store H(H(name)) and never name. If using H(H())Registrations of names must disclose the inner hash to prove that the key is a hash and not something else (or use a provable hash scheme). If you haven't guessed a name, or someone hasn't told you about it— it's none of your business that it exists.
Value data must always be stored as Enc(H(name||2), data). When a resolver returns a result, unless it has guessed a name it can't decode the update records. Only people who know the names have any business seeing a record. If necessary two levels of encryption could be used p2sh^2 style to prove that the data is encrypted at insert time.
The idea of the above measures is to strongly inhibit the use of the database as an anonymous broadcast communication channel and to allow resolver operators to be honest when they say they don't know and don't care about the specifics of their queries. It discourages some forms of censorship by at least requiring the censor to have become specifically aware of what they want to censor— you can't just go trolling the database for things that offend you.
Because of the UTXO tree data used in results a resolver couldn't lie and give an NXDOMAIN, but it could certainly return back that its refusing to answer a query for a particular name. If a resolver operator gets ordered to not serve a particular record, in spite of the above privacy, they can just return the hash of the record and a message saying its been censored.