If your NAT allows arbitrary connections out, and you're patient enough, you can probably finagle a peer to peer connection, eventually. Here's a discussion about that [1]. But that math is based on each NAT having a single external address; if your NAT spreads you over multiple addresses, the math gets much worse.

And there's a lot of other considerations; chances are your NAT won't be happy if you send all those probe packets at once, and your user may not be either. It's probably only worth it to do exhaustive probing if the connection is long lived, and proxying is expensive (in dollars because of bandwidth or in latency)

[1] https://github.com/danderson/nat-birthday-paradox/tree/maste...

The feasibility of this assumes one peer is always behind an endpoint dependent mapping. That's great if you only care about peers working with you and you control your style of NAT, but it's still pretty broken for the case you want this to work for any 2 peers. In practical terms, the success rate goes from something like the 64% with 256 probes down to something less than 0.01%.

If you can manage to bump it up to 65536 probes without getting blocked, hitting a NAT limit, or causing the user to fall asleep waiting, then it should hit the same success rate :D. I'm not sure many would like to use that P2P service though, at that point just pay for the TURN server.