If you read up on the PGP idea you will see that storing people's public keys is not an issue - they may be broadcast to the world. The clever bit is that they

If you read up on the PGP idea you will see that storing people's public keys is not an issue - they may be broadcast to the world. The clever bit is that they are combined with a private key (that you do not store or exchange) to encrypt and ultimately decrypt any given message or data.