I've been toying with an idea that changes the paradigm with respect to the two critical problems mentioned above: Just allow multiple registrations of the same name, and let the user disambiguate, and allow the user to "pin" the one that is relevant.

• Squatting would probably be solved, because common names that are over-registered would intrinsically lose value.
• Scamming might be solved, if people could distinguish by popularity rating.
• Relay records could be kept truthful by requiring updates to be signed by the owner as determined by the Bitcoin blockchain.
• This solves the problem of lost keys, because a new registration could simply replace an old one, and eventually the old one would become stale and drop out of relevance. (Of course such things as the popularity rating would restart, but that's probably a good punishment for losing one's keys.)