I'm not sure how you plan on doing it, but I think you should tie everyone's public keys to their names/id's. So let's say you know someone who uses Mailpile. You shouldn't have to ask him what's his key. You should just "enable PGP" (if it's not default, though maybe it should be), and he should just get the e-mail.

So try to do the key management as automatic and "out of the way" for users as possible. That's the biggest hurdle with using PGP right now.