The short version: Microsoft has a quota limiting the items that can be deleted in a given period in Exchange Online mailboxes.

When you delete an item from an Exchange Online mailbox, the message is first copied to the Recoverable Items folder (an entirely separate mailbox), and this mailbox has a quota, effectively imposing a limit on the amount of mail that you can delete in a period of time.

Microsoft has details here: https://learn.microsoft.com/en-us/exchange/security-and-compliance/recoverable-items-folder/recoverable-items-folder#recoverable-items-mailbox-quotas

  • "Recoverable Items quota are: a soft limit of 20 GB and a hard limit of 30 GB"

  • "If the Recoverable Items folder for a mailbox reaches the Recoverable Items quota, no more items can be stored in the folder. This impacts mailbox functionality in the following ways: Mailbox users can't delete items."

Users cannot remove messages from the Recoverable Items folder manually. The Recoverable Items folder is controlled by a retention policy which will delete messages after 14 days (by default), and no more than 30 days. To be clear, this is not the visible Deleted Items folder in the user's mailbox, and clearing deleted items will not help (rather, it will likely fail due to the same underlying issue).

At this point you can take one of a couple of approaches:

  • Wait two weeks

This is easiest, as it requires minimal action on your part; the recoverable items folder has a retention policy that will clear out the deleted content automatically.

If you want to avoid the error messages, you may want to temporarily change MailStore's archiving and deletion settings, perhaps disabling deletes or only deleting older messages, then adjust the settings back to what you would prefer after several days.

  • Reconfigure the recoverable items folder retention policy

Information regarding the Microsoft 365 retention policy is available at the following link, with links at the bottom for specific steps: https://docs.microsoft.com/en-us/exchange/security-and-compliance/messaging-records-management/default-retention-policy

If you do change the policy, remember that the retention policy processing only occurs periodically. You also should consider reverting the policy to default once any significant deletion events are finished to avoid future problems/confusion that could be caused by a non-standard configuration.