Basically, the problem is that PGP and S/MIME as they exist today are (and I shudder to say it) too security conscious. The reality is that most users are not going to take the time to maintain their public keys, to verify others' public keys, etc., nor are most users going to spend the time to get their keys verified by a CA. We need a "lite" PGP client that is less obnoxious about using untrusted keys, and basically a "newbie" PGP that is more vulnerable to active MITM attacks (which are actually much harder to pull off than one might expect). It would also be nice if public keys could be easily published via QR codes, so that someone can literally hand their public key to another person.
The worst thing we can do is lie to people about the security they receive e.g. telling them things like "Lavabit is set up so that nobody but you can read your email!"
Bookmarking reply
While someone might have their business cards replaced, it's a lot easier just to send a different key to someone.
Assuming that "private key" is a typo (you download public keys), you can just check the fingerprint of the key against the fingerprint you were given. That is easily automated.
A QR code can have ~4000 chars of a-z and ~3000 Latin1 iirc
so with my limited gpg knowledge that handles my public key quite happily.
would be interested on the business card front though
How do PGP and S/MIME solve the bootstrapping problem, where no-one uses them because no-one uses them?