Re: A better solution
Slightly dyslexic today, aren't we ?
Neither SIP nor RTP need to run directly on top of UDP. They can utilize an alternative datagram delivery service that is UDP-like, and this service will provide NAT travesal. It may in turn run on top of UDP, but that's optional.
This, my little patronizing friend, called virtualized layering, a concept that you clearly do not understand well.
A better solution
A cleaner solution is not to burden SIP (or any other application layer protocol for that matter) with NAT traversal logic, but rather handle the problem at a transport layer. Use generic tunneling service instead of UDP and let it worry about connectivity issues. Like Hamachi does it for VPNs for example.
I also believe you are wrong about Skype as it does seem to do a variation of UDP hole punching.