Basically I was not going to put up a list of everyones email addresses and keys anywhere, and certainly not who they connect with.
The more I looked into the problem, the more I realised that the vast majority of users would rather sacrifice security for usability. Even in my implementation people would rather not see the "Please verify this key with the recipient" page. They just want to get something done. I think this proposal from google would work well so long as their base implementation involves no additional steps beyond that of a normal email client.
I have the same problem of initial key exchange that everyone else does, but I give the user options to verify they keys themselves. Once they have they encrypt their own contact list (along with keys) and re-upload it. Therefore limiting the attack vector to initial key exchange.
If anyone wants to have a look check out http://senditonthenet.com/
The users private key is AES encrypted with the password as key and sent to the server for storage. A JSON hash of their contacts is also encrypted in the same way and sent to the server for storage.