NAT vs PMTUd

Greetings list,

We're troubleshooting an issue in which a client TCP connection is
initiated which passes through a firewall NAT, then into a router to
which a GRE tunnel is connected. The MTU of the tunnel connection is
smaller than that used by the client, so the router generates an ICMP
error type 3 code 4 (frag req'd and DF set), which encapsulates the IP
and TCP headers of the generating packet. But when that ICMP packet is
received at the client, it's ignored, and the client continues resending
at a too-large MTU until the connection attempt times out. The headers
encapsulated in the ICMP message include the client's NAT IP as the
source IP address, not its native IP. I suspect that the client
therefore ignores the ICMP message. 

Is it a common option on firewalls to re-write encapsulated headers to
avoid this sort of thing? How is this handled correctly? We've worked
around it by setting the client's MTU smaller, but we'd prefer to use
path MTU discovery and keep default MTU settings.

Any insights are greatly appreciated.

Dan Lynch, CISSP
County of Placer
Auburn, CA