I've thought about it for a little while and here are my high-level suggestions (I'm not a programmer and my understanding of Namecoin is limited):

* Only allow e-mail addresses to be registered as aliases and verify that the person who registers it has access to it. This can be automated like most mailing lists do. It is necessary to provide this basic level of security to prevent Bulanula from associating his wallet address with gavin@acm.org, for example.

* Make it independent of any coin (except Namecoin, obviously). Leave it up to the user to decide which coins to use and provide a secure data structure that any coin (existing or yet to be invented) can query to associate an e-mail address with a wallet address. While this feature isn't implemented by other coins it should still be possible to query Namecoin manually to list all the addresses for gavin@acm.org so that the right one can be copied and pasted into the client.

* Allow the aliases to be modified quickly in case somebody loses his wallet or changes his e-mail address. Also make sure that people get notified early on when it is necessary to renew their alias to keep it in the blockchain.

Is this possible?