Can I point out, however, that in doing so you're creating a fixed address to send money to yourself, thereby mangling a critical part of the anonymisation of BTC and similar?
Can I suggest it may be more practical to take the URL of the address on the Bitcoin Block Explorer (by searching https://blockchain.info/ ), then stuffing that through bit.ly or similar to give people something short to use?
Yeah, this can be always implemented as external services (which includes the bit.ly idea) which the Bitcoin wallets can utilize. But that wont be decentralized exactly.
About anonymity -- how will a DNS entry in the block chain revile information about it's owner?
I see this design --
The wallet will have an option to request a new DNS address which's to be associated to a receiving/sending address. The request process will broadcast the public key of the requester along with the DNS name, which'll also be signed to prove that the name belongs to this particular address.
The miners will accept the request and make such an entry in the block. This may include a high fee also to avoid mindless name registering, since verifying the new names may be a little computational intensive for all nodes in the network.
Before designing this, consider paper wallets also.
See, this idea works best at retail. So I tell the person on the cash counter that I'll be sending from address 'myname' to 'hisaddress'. No card swapping, no dictation of long case-sensitive addresses.