As Ron points out in the comments, typically larger enterprises won't have all of their outbound traffic sitting behind a single public IP but rather multiple pools of IP's that are often also at multiple gateways.
It's also the case that larger enterprises will often be using various app-level proxies for most outbound web traffic that, again, are typically broken up into different sites and clusters. As a result the NAT gateway/outbound firewalls likely would only see a handful of proxy addresses to be translated. These proxies themselves could have public addresses, or even be a managed service. Direct Internet access via a standard NAT gateway is often only provided on an exception basis, as the proxy approach has a bunch of other wins (caching, content management/security, load management, etc).
It's worth noting that even in the case of direct NAT there are usually fairly aggressive timeouts in place to recycle source ports.
Finally, ephemeral source ports can actually potentially be reused. Each socket is the tuple of (srcaddr, srcport, dstaddr, dstport, protocol). If any of those values changes, it's a different socket. In the NAT case, the same source port could theoretically be in use by multiple translations as long as there was other disambiguating information. So, for example, one session could be (Host-A, Port A, RemoteHost B, Port-B, TCP) translated to (NAT GW Addr, port-C, RemoteHost B, Port-B, TCP) while a session from another internal host to a different remote IP used the same ephemeral source on the NAT gateway.
Now...whether a given host OS or firewall implementation would bother reusing ephemeral sources this way? It's going to depend on the specific implementation. The key point is that the namespace is actually a lot larger than your question suggests.