I'm not sure there is no key exchange... Last I looked into Skype's security, not only was the traffic encrypted, the binary itself was also heavily obfuscated, so nobody knew what was going on. This was half a decade ago, though, and lots of things have changed since then.
That still doesn't change anything. There is (and never was) secure key exchange between contacts: if there was, it would be have to be explicit and you would've noticed.
The traffic might be encrypted, but the receiving party isn't the only one with the key. At the very least, the Skype service intermediated the key exchange.
