I've created Address Machine, a free public database to help people who need to pay each other in Bitcoins, but don't know each other's Bitcoin addresses.
https://www.addressmachine.com/It uses a simple, login-free process where you can look up addresses on the website, by email, by Twitter or through a web API. It confirms email address registrations before adding them to the database by sending a confirmation email.
Or you can use it from Twitter, for example:
Look up my address: @addressmachine @edmundedgar
Add your address (replace this with your own address, obviously...): @addressmachine 1Q4uC95NvGSw3JrmFAcc4ZDRDNGZ2u3bFT
Delete your address: @addressmachine DELETE 1Q4uC95NvGSw3JrmFAcc4ZDRDNGZ2u3bFT
I'll also add the ability to have the system create a temporary address for someone from the API and send them a key to access their wallet, so that you'll be able to pay people who haven't registered Bitcoin addresses yet. For now that will create an Electrum wallet, grab an address for it and send the owner the seed.
The code is open source (AGPL) and is designed with sharing in mind - for example, email addresses are stored hashed (I don't keep the plain text) so we can let a few independent people keep mirrors of the database, while reducing the risk that if they leak the data all the users get spammed.
More information on the website, detail in the README on GitHub.
https://github.com/addressmachine/addressmachineComments welcome, and if anyone's interested in mirroring the database, or has some confirmed identitifier<->Bitcoin address data they could share (eg maybe you run an e-wallet service), please get in touch.
