I have an interesting issue with my Exchange 2003 Server. It was working fine until last Sunday. Late Sunday we noticed that we can not receive an e-mail from a few vendors. We did other testing and notice that we can receive an e-mail from any users except the one who are using Office 365 as their e-mail server.

Any Ideas what might of happened?

Thank you in advance,

Serge

Hi,
According to your description, you can receive an e-mail from any users except the one who are using Office 365 as their e-mail server. 
I think office 365 server may list your domain into blacklist.
Have you received any NDR message when sending unsuccessfully?
Please post NDR here for further analysis.

In addiction I suggest we can try to upgrade the exchange 2003 to exchange 2010 or later version for best practice. And Exchange 2003 is out of extended support on 8th of April 2014.

Regards,
David 

Hi Serge, you have anti-SPAM or any antivirus in Exchange? View the quarantine or use message analyzer.