An alternate to IPv6 would have been to store the NAT addresses in IPv4 somehwere. But the IPv4 options are fragile and normal NAT would likely destroy them. It would still require rewriting all of the networking and software. It would have engrained NAT everywhere and made lots of routing problems, like is that your or mine 10. network.