Comment by throwawaykf02

I'm not sure what OP has against UPnP port mapping. It's not an ideal option and certainly not the best-designed specification, but it's a way to explicitly tell the NAT to do what we want, rather than having to trick it into doing what we want.

Also, one option not mentioned here yet is Teredo: http://en.m.wikipedia.org/wiki/Teredo_tunneling

It's primarily an IPv6 transition technology, but it comes with NAT traversal, hole-punching and all that built-in. What you get is a virtual IPv6 network interface to which you simply bind your socket, and you can connect to other Teredo / IPv6 sockets... if the whimsies of the Gods of Middleboxes allow.

What makes it attractive is that it is deployed on all Windows machines WinXP and later (and enabled by default on Vista and later), giving it a huge deployment base. It's not present on non-Windows machines, of course, but there is a liberally licensed implementation for OSX and Linux called Miredo. uTorrent is one popular application that uses Teredo.

However, Teredo tunneling does not work very reliably (apparently, its designers traded off connectivity for additional security), and it would be unadvisable to have that as your only NAT traversal method. But I think getting that option with minimal additional code is not a bad deal.