I'd like to hope the whole "web of trust" idea could solve this problem. If I've got a large enough set of people I've been sending signed or encrypted email too using a particular key, that history means I've got a pretty reliable idea that the key is "real". With a bit of luck, if enough of my set of people has their own group of historically-verified keys, I might have a good enough chance of finding someone I know and trust who'll vouch for a key fingerprint of someone I need to securely communicate with.
(I wonder if pgp signing registration email or payment receipts might help here? Or perhaps including key fingerprints? It'd be nice to be able to mail a user/customer saying "here's our PGP key, and you can check it against the key fingerprint we sent you when you signed up" or maybe " … that we print on every invoice" ?)
Widely communicating your key fingerprint makes sense. I put it on my business cards, etc. Back in the late 1990s people were talking about publishing root key fingerprints in newspapers, engraving them on stone tablets, etc. I.e. things which obviously required a lot of money be expended, thus making casual forgery less likely.
Perhaps people who rely on a longstanding online reputation could provide a service as verifiable online keystores for many different organisations via their own public key, so providing a distributed and multiply redundant public key resource that would be incredibly difficult to hack all in one go to fake a specific key.
