Do you have the public IP addresses directly on the MX units? If no, try and make it this way (much more reliable).
If you have to run the MX through NAT check the UDP timeout behaviour of the NATing router. If it times out too quickly it will break VPNs. A lot of consumer grade routers don't allow you to configure the NAT translation timeouts.