Yeah, I've run in to this. The point about NAT makes me wonder though if it is really de-prioritization or just the network straining to handle all that recalculation of checksums.
It's legal to send UDP packets with a zero checksum, indicating "no checksum." This can be set at a UDP socket level in Linux. I wonder if that would make any difference?
(Of course this assumes your protocol has some alternate method of verifying transferred data, which many do.)
(Of course this assumes your protocol has some alternate method of verifying transferred data, which many do.)