Even a 64-bit address would have been seen as doubling memory requirements of routing hardware for no good reason.
There could have been an optional 32-bit client sub-address ignored by the public routing backbone.
Then, for most purposes, non-backbone routers need two routing tables: a routing table for the public network (if more complex than a few simple gateways), and an organization-local internal routing table (with 32-bit addresses, just like the public table).
The actual problem is that each TCP/IP connection would require for the connection tuple (src_IP, src_port, dst_IP, dst_port) not 12 bytes, but 20 bytes.
Probably something could have been done to mitigate that, too, as things stood long ago, but I don't feel like speculating further just now.
Even without mitigation, let's suppose you have an FTP server and you want to guarantee at least 16 kb/s for each active FTP connection (circa 14.4/28.8 modem technology). You need to provide nearly a kbit/s network bandwidth per byte of connection tuple held in system memory (we'll ignore the messy nature of FTP, much of whose ugliness could have been averted by a better original IP design).
At the same time, NAT isn't all bad. It does help to conceal the internal structure of your network from the evil public network (and makes exposing your non-firewall hosts more of a sin of commission rather than a simple sin of omission).
NAT also erects a barrier to ultimate host fingerprinting and traffic analysis, at least until HTTP came along to ruin things with user agent strings and cookies.
Some people are quick to point out that a low barrier is no barrier at all, but I like to force my adversaries to at least put on their ballet shoes before attacking my network, and then to stay alert for people with trunks full of tools good at hopping low barriers.
My proposal doesn't much complicate the backbone routing table, except for Sandvine, who would have—once we got there—been pissed in a big way (counterfactually), to much rejoicing.