As long as IPv4x support was just something you got via software update rather than a whole separate configuration you had to set up, the vast majority of servers probably would have supported IPv4x by the time addresses got scarce.

However, if it did become a problem, it might be solvable with something like CGNAT.

CGNAT would also be easier on routers too, since currently they need to maintain a table of their port being used to the destination ip and port. Whereas with ipv4x, the routing information can be determined from the packet itself and no extra memory would be required

That's only true when forwarding IPv4x -> IPv4. When you're going the reverse direction and you need to forward IPv4 -> IPv4x, well, still need a table then.