Skype uses tcp-ip hole punching, basically trying to initiate a connection on both ends. guessing exit ports and trying to convince the firewall that this it received a response from the other side so it should start routing traffic to that port back.
The solution is not full proof and takes a few attempts to predict the outgoing ports.
1. Fog Creek's Co-pilot: Joel wrote about something similar
2. Skype: How skype connects calls even in the presence of firewalls