A significant wrinkle in how NAT works is IP fragmentation. UDP datagrams can be larger than an IP packet. When that happens the payload is split into multiple IP packets, but only the first packet has a UDP header in it. The NAT device needs to correlate these packets by looking at fragment IDs, and then rewrite the IP addresses in the headers. That alone implies a second kind of state to maintain, but it gets worse…
> Worst of all, this was all avoidable.
It is not that simple. To avoid fragmentation you need robust path mtu detection, which is another whole can of worms. Especially when packets can have multiple paths with different mtu.