Rule #1 of any client-server based encryption - you have to trust someone.
The normal flow of events is to sign a message digest with a private key. Given the corresponding public key, I can be gaurenteed the message is valid and it is from the person who sent it --- as long as I trust the public key. Now you could distrust the public key and do some type of db lookup. But PKC is set up so that as long as you trust the signer of the public
key (the cert authority), you can trust the public key. The only time you would
need to do any type of lookup was either the sender did not include the public key or if you failed to trust the sent public key. You could then do some type of database (ldap) lookup to retrieve a known, trusted public key for the sender.