So we acknowledge v4 and CG-NAT are a problem but don't want to use the already available solution because game developers took it upon themselves to DEFEAT NAT :)

That just reminded me of a peer protocol I worked on a long time ago that used other hosts to try to figure out which hosts were getting translated. Kind of like a reverse TOR. If that was detected, the better peering hosts would send them each other's local and public addresses so they could start sending UDP packets to each other, because the NAT devices wouldn't expect the TCP handshake first and so while the first few rounds didn't make it through, it caused the NAT device(s) to create the table entries for itself.

Was it Hamachi that was the old IPX-over-IP tunneling? I'm fairly sure it used similar tricks. IPX-over-IP is also done on DOSBOX, which incidentally made it possible to play Master of Orion 2 with friends in other continents.