Hole punching _can_ work, but again, it's exploiting implementation quirks in NAT devices and isn't a general solution (though it might do pretty well).
The only standard way (AFAIK) to open up NAT is via UPNP, which the client software (and NAT device) needs to support. The client then talks to the NAT device and tells it to port forward. It seems pretty common nowaday, and is more elegant and secure than the hacky "poke around and see what works" implementations.
Note the date, things are very different now.