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.