A TCP session is a unique combination of client IP, client port, server IP, and server port. So you can use the same IP and port as long as the destination is a different IP or port.

Fair point! I wasn't aware of any NAT working that way, but they could exist, I agree. It does blow up the session table a bit, but we are taking about a hell of a large theoretical system here anyway, so it's not impossible.

This wouldn’t help going to popular destinations, since they have a lot of people going to the same IP address and port, but for many (most?) of them you probably have some sort of CDN servers in your data centers anyway.

Actually we have recently seen a few content providers not upgrading their cache servers and instead preferring to fall back to our PNIs (which to be fair are plenty fast and have good enough latencies). On the other hand others made new ones available recently. Seems there isn't a universal best strategy the industry is converging on at the moment.