This is very similar to this problem:
I have a php script on an IIS server called example.org. It sends mail() to [email protected], which goes to a spam appliance and on to their Exchange server, but the mail never gets through. When I look in the logs there's an SMTP error saying user unknown or something, but the main point is that it's throwing an error as it's using the server specified in the second MX record, rather than the primary one. Consistantly.
Did a nslookup and the machine can look up the DNS and get the correct data, what's going on?