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.
To unsubscribe from the LSTSRV-L list, click the following link:
http://peach.ease.lsoft.com/scripts/wa-PEACH.exe?SUBED1=LSTSRV-L&A=1