I am running into a problem at work where end users are unable to email Hotmail or MSN email addresses. We are running an Exchange 2007 server and the message itself is in HTML and contains no attachments. If messages are sent to a distribution list, those recipients who use other email providers are able to receive and view the message. Now the kicker is that sometimes we are able to reach the addresses, though not with any regularity. For instance, a user may not be able to send a message in the morning, but will be able to in the afternoon or perhaps a couple of days later. Other times, we are unable to reach the addresses at all no matter how many times we try.
Here's some of the information that will get sent back during an unsuccessful attempt:
Delivery has failed to these recipients or distribution lists:
An error occurred while trying to deliver this message to the recipient's e-mail address. Microsoft Exchange will not try to redeliver this message for you. Please try resending this message, or provide the following diagnostic text to your system administrator.
The following organization rejected your message: snt0-mc1-f7.Snt0.hotmail.com.
Also, our mail server generates diagnostic information that the Hotmail (or MSN) server returned a "#500 Unrecognized command ##"
Has anyone encountered anything like this or know what the problem may be?
Update
I've looked at the issue a little more and it appears that the SPF record is good (or at least passable).
You may be getting caught in their anti-spam checks. According to the FAQ here: http://postmaster.msn.com/, you should publish your "Sender Policy Framework (SPF) records to help pass any Sender ID authentication checks."
Learn more about Sender ID and how to publish your SPF records here: http://www.microsoft.com/senderid
Make sure your reverse lookup on the MX record is there. They often times reject traffic without a reverse MX record to prevent spam
If you don't have an SPF record in DNS, consider adding it. I've found that to help. Apparently major players are starting to put some level of trust in domains that use it.
Don't bother adding a SPF record, but do remove an invalid one if you have one (or correct it). We find that more spammers have correct SPF records than non-spammers do (or rather, having a correct SPF record makes you more likely, statistically, to be a spammer)
DO make sure that your relay IP addresses resolve to something sane.
DO monitor IP address blacklists (RBLs) and get yourselves de-listed if you suddenly become listed.
DO monitor your volumes of outgoing mail in case you have spam-bots or open relays internally. Most antispam services will only store your IP address reputation for a finite time and give you a chance to improve it - the only way of remaining persona non grata is to continue trying to send them spam.
It might be worthwhile routing outbound traffic from internal staff machines and non-critical mail servers etc, so that it is NAT'd through a different address from your own mail server(s) - this ensures that if your other machines suddenly start sending spam, it doesn't impact your users. You should of course monitor all your public IPs anyway for blacklisting.
I don't know if anyone actually uses SPF for spam-prevention - but if they do, I don't know why - it's absolutely useless (in fact, you can use it the opposite way - having a correct SPF record makes mail more likely to be spam).
(I work for an antispam company).
We see the same behaviour. Hotmail/MSN check for SPF records (all ISPs these days are checking email reputation of the domain and IP Address of the sender before accepting delivery).
Create an SPF record on the domain that you're sending emails from (use the wizard at http://www.openspf.org/ ). Once it's set up test the SPF record by sending a mail to a gmail account and view the message headers of the email and you'll find Google reports on the SPF result:
Check that you have reverse DNS entries for each of your MX records - http://www.dnsstuff.com is good for checking these are setup. While you're there check you're not on any blacklists (but I think you'd see a different error message if you were).
I'm not sure if the server's name makes a difference (needs to be set to the same as the reverse DNS entry?)
If you are routing email from your LAN via a WAN (external) IP address that is not listed in your domain's MX records, then a majority of spam solutions will flag your email as spam. Adjusting your SPF records to include these WAN IPs would defintely help the situation.