Antonio Nucci, CTO of software firm Narus writes here about the Challenges In Detection of Skype Traffic.  Of course don’t expect them to give away too much detail on trade secrets, but the general approach described is not to decode or reverse-engineer the protocol, but rather to profile traffic using a heuristic approach. 

Firstly, he talks about signature analysis of the TCP, UDP packets, and then about analyzing/profiling the behaviour, for example traffic patterns.  How this can be done in a way that is CPU-efficient and with a low rate of false positives, he does not say.

Narus is one of the companies that has been linked with the Shanghai Telecom story, regarding the blocking of VoIP traffic.  It is not clear whether Shanghai have in fact bought Narus’ Skype-blocking module.