I see this from time to time for customers using Office365... Can't explain it, often a reboot fixes it as well.
(Take with grain of salt) Someone told me once this is related to the fact that the IP addresses changes often for the O365 servers, and sometimes DNS caching at some level in the name resolution hierarchy can cause this to break. Since a reboot or change of some kind on the 5000 causes it to work, it could be the 5000 us using DNS caching of the server's host name and trying to talk to an old IP address associated with the hostname.
TBH, of the few customers we have on Office365 with a 5000 system (6-10 or so) about half have switched to Forward & Copy for reliability. The ones that still use it, I typically setup to reboot at least weekly.