EWS Operation Item.Copy fails with 'full_access_as_app' permission

We have been using the EWS Item.Copy Operation for nearly 5 years. Since last week (Monday 26th of February 18:00 CET) this operation started failing for 2 of our 40 customers. No configuration has changed in Azure. App Secrets and API Permissions are setup correctly and consent has been given once more to be sure. We ask our customers to grant us 'full_access_as_app', which should be enough for the EWS Item.Copy Operation and this has been enough for years.

Unfortunately for 2 customers the EWS API is denying us acces. I can get the message to be copied and I can get the target folder I want to copy the message to. But a copy operation throws the following error:

reason="Access to this API requires the following permissions: 'MailExport-Internal.Read.All,MailExport-Internal.Read.Shared,MailExport-Internal.ReadWrite.All,MailExport-Internal.ReadWrite.Shared'. However, the application only has the following permissions granted: 'full_access_as_app'." error_category="invalid_grant"

Does anyone know how to fix this problem?

I have tested that I can get the message and target folder through the EWS API using Postman. I have renewed the App Secrets. I have checked all permissions requested and consent has been withdrawn and given to be sure. I have created a new mailbox to test if the target is an issue.

The problem still persists, even between other mailboxes and folders.