Indeed. For those that started scratching their heads 'this is impossible', this deep dive from the Tailscale blog will be informative. Perhaps even entertaining, the birthday paradox may have a hand in it.

https://tailscale.com/blog/how-nat-traversal-works

However in situations where you have say a Juniper SRX scrambling both source and destination ports on both sides of your nat, the birthday intersect is 2^32 rather than 2^16.

With a Cisco ASA or Fortigate which tends to keep the same source port where possible you'll converge far more quickly. When there's a central server to help it's even quicker and most of the time will just work.

(sometimes it's not possible to keep the same port when source-natting -- with two devices from 192.168.0.1:9000 -> 1.1.1.1:53 and 192.168.0.2:9000 -> 1.1.1.1:53, the second will have to have a mapping to non-:9000 source IP, but in my experience, Cisco, Fortigate and Mikrotik (thus linux) all support the "only change if needed" option)