On April 6, sometime after midnight, it appears that Exchange Online made a change that effects the EWS throttling policies.
As of 9am CST today, we have 275 tenants with this problem.
The error looks like this:
[You have exceeded the available concurrent connections for your account. Try again once your other requests have completed.]
ErrorDetails; Key=[Policy], Value=[MaxConcurrency]
ErrorDetails; Key=[MaxConcurrencyLimit], Value=[27]
ErrorDetails; Key=[ErrorMessage], Value=[This operation exceeds the throttling budget for policy part 'MaxConcurrency', policy value '27', Budget type: 'Ews'. Suggested backoff time 0 ms.]
At this phase of processing., our SaaS platform has only a single thread (no concurrency) and our backoff time is ten minutes.
We made the request to remove throttling policies for 90 days on our own tenant. The support request suggested that we wait 15 minutes for the policy to be updated.
We waited 24 hours and the same error appears.
Microsoft support has not been so helpful.
Microsoft Case 35934803