I hate to inject gloom and doom into a fun topic like vanity bitcoin addresses... but y'all should be aware that one of my longer-term goals for the Bitcoin system is to make bitcoin addresses disappear. I hope Bitcoin software 10 years from now tells users "You're about to pay 11 micro-Bitcoins to Amazon.com" and not "2mRwtf8blahblahblah". And I'm not alone, I know Mike Hearn feels strongly about making bitcoin addresses go away for ordinary users.
If you do spent lots of time creating The World's Best system for mining vanity bitcoin addresses, please don't be upset or surprised if you find it is obsolete when "Bitcoin 2017 Turbo++ Enhanced Edition" is released.
The foundations seem napkin-sketched out already from
Mike's post; I've started thinking it through, and a self-published alias might be the easiest addition. It would seem best to lift Namecoin's style of address registration
with fee. There would certainly be a landrush period, and you would want to discourage squatting, so a significant but diminishing cost would better ensure interested parties might still find their desired alias available (see
post #10 above; I paid .55 BTC in fees just for some fun...).
Implementation: You go into your address book, there is an option called "register label on network". You press this, it asks you to create an alias that other clients can see to send money to you. If you are not the first, you get an error that the alias is already taken. The alias is permanently included in the blockchain along with some bitcoins you donate as the fee, and then the address book will list all aliases registered to your address. Other Bitcoin clients would have a searchable database of all these aliases to find you as a recipient.
However, I don't think anything like this should be included in Bitcoin. Although not any more dangerous than "firstbits", it would make it too easy to spoof people into sending money to an "amazon.com" that goes to a malicious squatter instead. It also hinders anonymity and the sender identification that comes with one-time-use addresses.
