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).