En esta larga noche sin dormir, [...]

Let A and B be the two hosts, each in its own private network; NA and NB are the two NAT devices with globally reachable IP addresses EIPA and EIPB respectively; S is a public server with a well-known globally reachable IP address.

A and B each begin a UDP conversation with S; the NAT devices NA and NB create UDP translation states and assign temporary external port numbers EPA and EPB
S examines the UDP packets to get the source port used by NA and NB (the external NAT ports EPA and EPB)
S passes EIPA:EPA to B and EIPB:EPB to A
A sends a packet to EIPB:EPB.
NA examines A's packet and creates the following tuple in its translation table: {Source-IP-A, EPA, EIPB, EPB}
B sends a packet to EIPA:EPA
NB examines B's packet and creates the following tuple in its translation table: {Source-IP-B, EPB, EIPA, EPA}
Depending on the state of NA's translation table when B's first packet arrives (i.e. whether the tuple {Source-IP-A, EPA, EIPB, EPB} has been created by the time of arrival of B's first packet), B's first packet is dropped (no entry in translation table) or passed (entry in translation table has been made).
Depending on the state of NB's translation table when A's first packet arrives (i.e. whether the tuple {Source-IP-B, EPB, EIPA, EPA} has been created by the time of arrival of A's first packet), A's first packet is dropped (no entry in translation table) or passed (entry in translation table has been made).
At worst, the second packet from A reaches B; at worst the second packet from B reaches A. Holes have been "punched" in the NAT and both hosts can communicate.
If both hosts have Restricted cone NATs or Symmetric NATs, the external NAT ports will differ from those used with S. On some routers, the external ports are picked sequentially making it possible to establish a conversation through guessing nearby ports.