This is a classic PMTUD black hole. Type 3 Code 4 is the only signal that tells the sender to lower its MTU, so without it the Gateway keeps emitting at 1500, oversized EDT packets are silently dropped, and since UDP has no retransmit the loss stays invisible and the step down to ~1380 never happens.
The Gateway Service path is not the problem: it starts from a conservative MTU, which is why it does not black-hole. It is the on-prem path that optimistically starts at 1500 and never learns to reduce.
For the firewall change: scope the rule to Type 3 Code 4 inbound to the SNIP/VIP, not all ICMP. You cannot source-filter it, since the message is generated by an arbitrary router along the path, so use a rate-limit instead. If you have IPv6/DS-Lite, also allow ICMPv6 Type 2.
After deploying, verify with
ctxsession.exe -v
on a VDA behind the on-prem Gateway: the EDT MTU should settle at the real path value and the loss counters should stop climbing.