Wow, sorry for the diversion...but I do suggest following up with the MSS stuff as discussed in this thread...a must for GRE/IPSec. Your problem smacks of DNS...like the DNS servers you use cannot find the MX entry of the destination domain...but I'm...
Yeah, you're probably right on both counts there...but I noticed that when putting MTU commands on my tunnel interfaces, I would often get an error saying that the value was greater than the default of 1394, and my rule of thumb for mss was 40 bytes ...
Does your WAN consist of GRE/IPSec tunnels? The additional encapsulation overhead can exceed interface MTU, especially for applications that use large efficient packets, like printing, FTP, mail, remote desktop, active directory synchronization, etc....