Solving PMTU problem would have required reifying the MTU to the IP layer. It could have been done like this:
1. Use a 16-bit field in the non-checksummed portion of the IP header. Initially this field is set to the MTU of the link that originates the packet.
2. Each router inspects this field, and sets it to the MTU of the next hop link, if it is lower than the MTU already in the packet. This will be cheap, as the field is not checksummed.
3. If the packet is bigger than the MTU of the next hop, just truncate it, and set a special bit somewhere in the packet header to indicate it. No need to recalculate the checksum either, the packet is going to be corrupt anyway.
4. The destination host gets the discovered MTU of the forward path, and sends it back to the originating host in the header of the next packet (in a checksummed part).
That's it. Easy, continuous MTU discovery, with robust handling of failures, that doesn't require any smarts from the routers (a comparator to update the MTU can be done in a few logical gates!).
Alas, nobody had the presence of mind to think about this back then.