There is no secure method of exchanging public keys using only the net. [spoofing, etc.]
As mentioned by Hal, the new PGP 2.1 (imminent) has a feature to create an hash or a public key which can be read over the telephone to make sure that a key transmitted electronically has not been altered in transmission.
[long business description deleted]
There's really no need for a physical authentication service with the telephone verfication ability.
Plan B is to exchange/verify public keys face-to-face at parties,
There is just such a plan underway to have a PGP key exchange table at Usenix in January.
I have printed up business-card size copies of *fragments* of my public keys with the 6-hex-digit "Key ID".
What could easily be printed is the hash function of the key. That would be even harder to duplicate. Eric