Yeah, key exchange is always hard. You need to use a secure channel for that, we found a OTR-encrypted jabber-message the easiest way to go.

Sadly, RetroShare didn't really work for us. The UI is too clunky and the software has too many weird issues, like reindexing all files occasionally.

Then you need to secure the OTR channel, i.e. authenticate the remote users; the same goes for using PGP-encrypted email – in both cases, it is almost impossible to securely authenticate someone who isn’t sitting next to you.

Yes, you should do this. Mechanisms for authentication of OTR-chats is build into the usual plugins (exchanging a secret). It is not almost impossible - in doubt, just call him.

Exactly. One phone call to verify the signature is all you need. Skype (or any other insecure (against passive attacks, i.e. the attacker shouldn't be able to modify what's going between you) channel) will work just fine, as long as you can be sure you're talking with the person you think you're talking to.

Yes, if you compare fingerprints, then the important point is to authenticate both sender and content of the message. ‘Common Secret’ authentication as it is supported by OTR with Skype as the channel to negotiate that secret won’t be any good, nor will Skype text chat be sufficient to authenticate the sender of the message.

If it absolutely has to be remote, I’d go for a combined audio/videocall on Skype where one reads out the fingerprint and holds up a (ideally hand-written) sign with it – though I’d still prefer IRL-authentication (plus it’s more fun! :)), and ‘only authenticate keys in real life’ looks like a helpful rule-of-thumb to me.

Why is just reading the fingerprints to each other via video chat insufficient?