For years we've struggled with poor skype quality when working with the corporate office users. For years, the network team has tried to troubleshoot any possible contributions to the problem. Since skype works GREAT for me whenever dealing with someone not in the office, it must be a problem with the office.
Turns out, we were chasing the wrong problem the whole time. The problem is that skype was designed for 1 to 1 communication between consumers, not a business network. So using the consumer version of Skype, the data transmitted is handled differently. In geek terms:
The solution? Upgrade to skype corporate which is designed for this traffic or use an alternative like GotoMeeting or other tool which is not based on a UDP P2P connection.
The lesson for you in this is that you can blame the technology all you want. However, sometimes it is doing exactly what it was designed to do.