Recently, senders from Hotmail have begun to get the following NDR when trying to e-mail our domain.

EDIT : Full NDR Message

Action: failed Status: 5.5.0 Diagnostic-Code: smtp;550-Please turn on SMTP Authentication in your mail client, or login to the 550-IMAP/POP3 server before sending your message. 550-snt0-omc3-s36.snt0.hotmail.com [65.55.90.175]:49271 is not permitted to 550 relay through this server without authentication

This is seemingly out of the blue and I'm at a loss as to why this is happening.

Pertinent Information

• We have multiple domains hooked up to our Exchange server. We changed our company name in January of this year, and the old primary domain (olddomain.com) will accept e-mails from Hotmail accounts, however e-mails sent to the new primary domain (newdomain.com) bounce back with the NDR listed above.
• The bounces only appear to be happening when the Hotmail sender is sending a new e-mail, and not if they are responding to an e-mail sent from our end.
• We have made no changes to the configuration of our server recently. This e-mail first appeared last Friday.
• As far as I can tell, the mail doesn't even seem to get to our server
• We performed an Exchange 2003 to 2010 migration last year. The 2003 acts as a Smart Host

Any advice on this issue would be greatly appreciated! I'm at a loss