I have a recent install of Exchange 2013 with mail filtering through a Sophos UTM, everything works as it should, except I have one domain that cannot email mine, and my domain cannot email it. Both of these servers reside in the same geographical region, use the same ISP, and use public static IP addresses that only differ by the last octet (though they reside on different subnets).
DNS can resolve the exchange server I am trying to send to however emails queue and eventually end with an NDR.
SPF records are set up properly with external DNS provider.
"Remote server at ________ returned '400 4.4.7 Message delayed' <date and time> - Remote server at ______ returned '441 4.4.1 Error encountered while communicating with primary target IP address: "Failed to connect. Winsock error code: 10060, Win32 error code: 10060." Attempted failover to alternate hosts. The last endpoint attempted was <IP address of their domain:25'
Originally thought this may have been an issue with PTR records, had the ISP fix the PTR records for both of the company's Exchange servers, however that change did not resolve the issue. At this point I have run out of ideas.