OK, That's really strange. The internet connection troubleshooting sent me down a particular path and I remembered that many years ago, the subnet we had from our ISP was split into two halves with one half being NAT'd on our old Checkpoint firewall, and the second half of the subnet routed through the Checkpoint. No idea how, I never saw the config.
However, switching to 3 IP addresses in the original lower half of the range has the MX's happy again. It's bizarre as there are services using the upper half without issues..
But anyway, we are up and running.