Try an NSLOOKUP type=MX on the recipient @host.
That can be very telling.
You may need to telnet port 25 to each of them and begin a
simulated RFC821 dialog. Maybe a VRFY will fail.
In my former career, I've seen misconfigured MX hosts that would
only be a problem when the preferred host wasn't available.