The whole point of PGP is to actually communicate (out of band) with the party you want to sent mail to and receive his public key.

It's no big deal if you really need to send a private message.