Several customers of our software libraries have reported many occurrences of what appears to be the same issue on August 24th and 25th . In all cases, the error occurs when accessing an O365 mailbox using EWS with app-only OAuth authentication. Eventually, after a while (usually several seconds, but sometimes minutes or even hours), the same EWS request that initially got rejected (with ErrorInternalServerError) succeeds.
We have been able to reproduce this issue by accessing a mailbox using app-only authentication that has not been accessed before (or that has not been accessed for several months). However, our customers reported encountering some mailboxes where the issue persisted for hours. One of the customers reported having used app-only authentication for years without ever encountering this error before August 24th
Based on our observations and other error reports here, we assume this is a server-side issue. However, some clarification from Microsoft would really be appreciated.