"UDP hole punching does not work with all types of NAT..."
I think what you mean to say is the STUN and TURN solutions do not work.
What else have you tried?
I personally do not use those solutions.
The last resort is for a peer outside the problem NAT to forward traffic.
This is not true peer-to-peer (IMO) but it does work.
If what you suggest were true, that reliable peer-to-peer is "impossible" because of some types of NAT, then how do you explain the success of Skype?
If you give specifics about what exactly you were trying to do, and what exactly you did to try to accomplish this, maybe someone could offer suggestions.
I already knew that STUN and TURN have problems. That's why I do not even bother with those "solutions".