The remark about cryptographic authentication in probe packets is the key. The attacker mustn't know what your packets say, or be able to fabricate or (important!) save and re-use what it has seen before.
It involves lots of public-key encrypted random numbers carried in the probe packets. You discard packets that don't match your expectations, and you are safe(ish). If you have to avoid too much public-key encryption and decryption because your cores are slow, it gets more complicated, like establishing beach-heads and using symmetric encryption and, still, random numbers between those while establishing the next level up. But cores are usually fast enough nowadays, even on cheap routers and IOT SOCs.
I'm not sure I understand how can cryptographic authentication completely solve that problem, as it is only validated on the endpoints themselves, not on the router.
As long as you have a signal that probing has started, you can just start sending probes : even if their contents are not validated, the NAT device will still define mappings accordingly. The probability distribution for the birthday attack in this configuration is a bit different, but not that much : for 3 devices to get to the same port number, at 4096 probes you get a ~93% probability.
The only way I see would be blocking probes that match an already-received invalid probe, but that creates other problems as it allows an attacker (or even just corrupted packets) to block this communication.
It involves lots of public-key encrypted random numbers carried in the probe packets. You discard packets that don't match your expectations, and you are safe(ish). If you have to avoid too much public-key encryption and decryption because your cores are slow, it gets more complicated, like establishing beach-heads and using symmetric encryption and, still, random numbers between those while establishing the next level up. But cores are usually fast enough nowadays, even on cheap routers and IOT SOCs.