For a clean room reverse engineering they could analyse the Skype binaries to document the protocol.
What's required (for purposes of courtroom defense) is a clearly documented procedure in which those who have access to the source being reimplemented (the spec writers and testers) NOT be the coders, and vice versa.
Another example is the SMB/CIFS reimplementation in the case of Samba. Here, because the protocol was an over-the-wire system, analyzing network packets (not covered by source analysis proscriptions) was sufficient to create a Free Software implementation.
Software patents are intentionally vague, so I doubt anybody could write a working client based on a patent alone (even if whole protocol was claimed to be described).