> my previous employer had like 20,000 employees NATed behind a single IP.

If so, it’s incredibly unlikely that all 20k were online simultaneously. If they were, each person could only open ~3 TCP sockets to the internet (even if via a proxy if dealing with individual login sessions) at a time before you’ve run out of ports.

even though you're probably right on the first part, the second part is false. while most NAT implementations operate as you describe, called "port-restricted cone NAT", some implementations allocate the external port only for a specific destination address, called "symmetric NAT".

TIL, thanks!