Incorrect. Skype relays media via other users when two users cannot directly connect. So if you and I are behind proper NATs, and no negotiation works, then we agree on a nearby (super?)node that is accessible, and relay media through there.
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.
