All you should need is for both sides to connect to each other. Side A connecting to side B opens a hole in side A's firewall and is blocked by side B, then B connects to A, opening B's firewall and going through the already open hole in A's firewall.

It might work better with UDP but I don't think those firewalls boxes tear down the mapping immediately on getting an RST - they wait until it times out.