Network address translation is the bane of P2P. There's a black art for establishing UDP communication between two peers behind NATs by having a third party introduce the peers and fooling the NAT routers into routing the packets. Games have been doing this for a few years. I see now it's well documented by Bryan Ford.
Bryan also has a draft RFC for NAT P2P. It's a great document and includes a technique I'd love to see developed further: opening TCP connections through NATs with a "simultaneous open":
If, however, the SYN packet arrives with source and destination addresses and port numbers that correspond to a TCP session that the NAT believes is already active, then the NAT will allow the packet to pass through.It requires predicting TCP sequence numbers, though, so I fear it's impractical.
As seen on decentralization