Interestingly, I noticed the same 500 error pop up once in our automated tests for O365 access overnight. It only occurred once when the test run started, but all subsequent tests passed without issues. The mailbox used by those tests is not new, but those particular tests have not been run for over a month (and the mailbox has not been accessed by any user or app in the meantime), so perhaps Exchange Online decided there is no need to keep the mailbox ready for instant EWS access, and reverted it back to "not accessed by EWS" mailbox. (Just speculating here... Hopefully Microsoft would clarify this, if you are able to get through all their layers of support.)