[drdaeman]

> I don't think NAT piercing works if both of the endpoints are behind NAT

It does, in many cases even without on any third party. That is a (mostly) solved issue for at least 5 years or maybe even more. Here are examples of such tools: http://samy.pl/chownat/ and http://samy.pl/pwnat/

There are cases such tricks won't work (like overly conscious connection tracking engine and all ICMP traffic blocked - but without ICMP one would have PMTU issues and those ain't fun), but there're always STUN and TURN. The distinction is, those is not middleman, but just a NAT piercing helpers. They don't pass your traffic through and they're generic and useable with any service.