Does anyone knows, how skype redirect NAT and FireWalls?
I believe Skype uses a variant of the STUN protocol to traverse NAT.
You can find example C# code to implement a STUN client here.