We had a problem with our Exchange Server 2003 last week and still am not sure we have recovered from it. It started with some of or customers that use Proofpoint. Proofpoint did an upgrade last week that that stopped people that use it from sending to our Exchange Server 2003. The upgrade refused to send to any mail server using RC4 cipher and that is Exchange Server 2003.
Now it looks likes something is going on with Office 365. People using Office 365 for some reason can't seem to send to our Exchange Server 2003. There are no signs of errors on the Exchange Server. They are getting emails from other outside sources. I just sent four users a test from my Outlook 365 account and it doesn't look like it is going to show up.