"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".
You make the problem sound like it's lack of IPv4 address space.
That is true in some respects because the method of allocation of these addresses is not straightforward and has its own set of problems.
But in actuality "the problem" the OP is encountering is that for the RTC developer/user, a publicly reachable IPv4 address block is too expensive.
With a publicly reachable IP address (most ISP's will provide one, often for an additional fee), you can do peer-to-peer quite easily.
UDP hole punching works fine, save for when both peers are behind the same NAT, in which case you need a peer outside the NAT to forward traffic.
And it's easy to simulate a LAN over the internet using encapsulation.
Gamers have been successfully hole punching for many years.
I'd say up until recently, gamers have really been the only group that has demanded peer-to-peer connectivity and made it work.
One wonders if every ISP customer were willing to pay the extra fees (if any) and requested a publicly reachable IP address, could the ISP's meet the demand?
Nor does NAT piercing require a web browser.