Earlier quoted context omitted.
But how would you verify that YourFacebookFriend is YourFacebookFriend on some other service?
This is a solved problem, but not one that would catch on. See: PGP If my friend can sign a message using the same key on both services - and I already trust that key is them - I can be almost certain it is them. Regardless of the service. This is one of the first use cases for keybase.io - verifying identities across a few main social sites. (E: For clarification, Keybase makes it easier to find these proofs. It isn…
It's only 'solved' if you don't care about usability. PGP quickly becomes a nightmare when you consider the day-to-day things 'normal' computer users will go through (private key stolen, password to private key forgotten, phishing attacks to sign replacement keys for friends, etc).