If you don't control the NAT device, there's obviously no way to bypass the NAT device. All traffic is going to be NAT'ed no matter what. In this case, there's no way to tunnel through since what you're trying to connect to isn't doing any tunneling. Regardless, even then, I don't think it would help.
This sounds like poor network connectivity due to packet loss. Every app you specifically listed aside from p2p and FTP uses UDP, a connectionless protocol that does not guarantee the delivery of packets. FTP also has some funny business using multiple ports that can be an issue with overwhelmed NAT devices.
Your contractor may have a NAT device that is simply overwhelmed for the amount of traffic it is passing, or the contractor may also be using multiple NAT devices chained, a configuration called "double NAT", which causes endless issues.
Given these circumstances, and due to the fact you don't know where you're actually downloading files from via p2p, this explains all your p2p issues.
A couple of things you could try though to confirm or alleviate the issues as best as possible.
A. Get the ip address of a game server, and ping it repeatedly using ping (ip addy) -n 100 so you can see if you're getting inconsistent responses. If you do, that's related.
B. Lower your default packet size. You could be having issues with packet fragmentation.
http://www.winguides.com/registry/display.php/280/
C. Run some tests from sites that offer the service for free, such as...
http://www.dslreports.com/linequality
Hope this helps.
"Milk was a bad choice!"
