It is not true that all counterproposals are impossible to deploy, they just have a number of downsides that were either politically or technically impalatable in 1996. For example, the network could have been made administratively compatible (same config files, DNS entries, routing prefixes) for a decade while a variety of internal changes and updates took place as part of the normal upgrade process.
I do not mean no changes at a binary level, but at an administrative level. An upgraded "A" record for example so that DNS admins could go about their day somewhere between completely and largely unaware that the protocol was undergoing transparent upgrades behind the scenes while preserving administrative compatibility with all existing configuration files, source data, and user interfaces. In such a scheme it would be quite important that there only be one "A" record from an administrative point of view, not different ones like A and AAAA. Admins need to be insulated from the binary protocol changes going on behind the scenes.
That means that the new address format would need to be compatible with the old one, and of course a routable embedding of the current address space be provided in the new address space. That means existing routing prefixes would have to be preserved indefinitely, complete with the routing table explosion that was a major challenge a couple of decades ago.
All routers would need to be upgraded over the transition period to handle a new frame type that supported current addresses, extended addresses, and a single routing table with larger extended address sizes. It is quite important that there be a single routing table, not two of them. Same configuration file, same everything from an administrative point of view for a decade, while older hardware was gradually replaced with new hardware that had extended capabilities that would be dormant on the public net.
Comparable and in some cases less transparent updates would need to be made to programming APIs, and to the Berkeley socket API in particular. Not to require programmers to do everything for two different layer 3 protocols, but rather to allow them to do it once and have it work with current and extended addresses, transparently from an administrative point of view, not doubled configuration for anything.
There are many other things that would need comparable binary behind the scenes upgrades that would be administratively compatible and not affect current network configuration files, and in particular not require anything to be duplicated from an administrative point of view. No one does that and no one wants to for protocol extensions that are not actually usable yet. It doubles their workload with no short term benefit, and does so indefensibly.
And then after all these extensions and capabilities have been designed, implemented, and transparently deployed across essentially the entire Internet without requiring large scale administrative intervention - a process that could easily take a decade - would the first extended addresses with non-zero bits in the extension fields actually be usable and globally routable in both directions. The entire network would be ready for it, it would be a dormant capability unused until that day arrived and requiring no large scale intervention when that day arrived either, because the silently upgraded network would remain administratively compatible with the old one.