Unable to delete items from mailbox / Unable to delete items from calendar.

If you encounter the following type of issue: a user is not able to delete items from his mailbox (emails or calendar items), please follow this article and apply the proper steps to solve it.

Error message samples:

Remote Server returned '554 5.2.0 STOREDRV.Deliver.Exception:QuotaExceededException.MapiExceptionShutoffQuotaExceeded; Failed to process message due to a permanent exception with message Move/Copy messages failed.

Task 'user@contoso.com’ reported error (0x8004060C): 'The message store has reached its maximum size. To reduce the amount of data in this message store, select some items that you no longer need, and permanently (SHIFT + DEL) delete them.'

- First check if the mailbox is placed in on Litigation Hold or it is part of an In-Place Hold Search. In this situation the deleted items are put on hold and are not purged from the mailbox.
Get-Mailbox <affected_user's_mailbox> |FL Name,LitigationHoldEnabled,LitigationHoldDate,LitigationHoldOwner,LitigationHoldDuration,InPlaceHolds

Example:
Get-Mailbox admin | FL Name,LitigationHoldEnabled,LitigationHoldDate,LitigationHoldOwner,LitigationHoldDuration,InPlaceHolds
Name: admin
LitigationHoldEnabled: True
LitigationHoldDate: 06-Jun-14 12:00:45 PM
LitigationHoldOwner: admin@cobarz001.onmicrosoft.com
LitigationHoldDuration: Unlimited
InPlaceHolds: {cf41064a75a746319ae30862527697c6}

If the mailbox is part of an InPlace Hold Search, more details about it can be found with command:
Get-MailboxSearch -InPlaceHoldIdentity <ID_found_in_previous_command> | FL

- Second check in PowerShell if the TotalDeletedItemSize is near or has reached the maximum amout of 100 GB.
Get-MailboxStatistics <affected user's mailbox> | FL Name,DeletedItemCount,ItemCount,TotalDeletedItemSize,TotalItemSize
You will see something like:
DeletedItemCount: 299030
ItemCount: 18457
TotalDeletedItemSize: 100 GB (107,374,361,974 bytes)
TotalItemSize: 1.016 GB (1,090,836,681 bytes)

In your case there are 2 possible solutions:
- remove HOLD from the mailbox and delete unneeded items (not recommended). Please user this option with care. The mailbox was put on Hold for certain reason. This option will trigger execution of the retention tags and the deleted emails will be purged. Valuable data might be loss.
- enable online archive (for E3 / E5 license, available for user with no additional costs). In this way, the old emails will be moved automatically from the mailbox to the archive.
********************
********************

Allow me to explain a few elements to better understand what is happening:

About DELETION:
- Delete -> Describes when an item is deleted from any folder and placed in the Deleted Items default folder.
- Soft delete -> Describes when an item is deleted from the Deleted Items default folder and placed in the Recoverable Items folder. Also describes when an Outlook user deletes an item by pressing Shift+Delete, which bypasses the Deleted Items folder and places the item directly in the Recoverable Items folder.
- Hard delete -> Describes when an item is marked to be purged from the mailbox database. This is also known as a store hard delete.

To protect from accidental or malicious deletion and to facilitate discovery efforts during litigation or investigations, Exchange Online use the Recoverable Items folder.

By default, when a user deletes a message from a folder other than the Deleted Items folder, the message is moved to the Deleted Items folder. This is known as a move. When a user soft deletes an item (accomplished by pressing the SHIFT and DELETE keys) or deletes an item from the Deleted Items folder, the message is moved to the Recoverable Items folder, thereby disappearing from the user’s view.

Items in the Recoverable Items folder are retained for the deleted item retention period configured on the user’s mailbox database. By default, the deleted item retention period is set to 14 days for mailbox databases. If a mailbox isn’t placed on In-Place Hold or Litigation Hold, items are purged permanently from the Recoverable Items folder on a first in, first out basis when the Recoverable Items warning quota is exceeded, or the item has resided in the folder for a longer duration than the deleted item retention period.
********************

The Recoverable Items folder contains the following subfolders used to store deleted items in various sites and facilitate In-Place Hold and Litigation Hold:

Deletions -> Items removed from the Deleted Items folder or soft-deleted from other folders are moved to the Deletions subfolder and are visible to the user when using the Recover Deleted Items feature in Outlook and Outlook Web App. By default, items reside in this folder until the deleted item retention period configured for the mailbox database or the mailbox expires.

Purges -> When a user deletes an item from the Recoverable Items folder (by using the Recover Deleted Items tool in Outlook and Outlook Web App, the item is moved to the Purges folder. Items that exceed the deleted item retention period configured on the mailbox database or the mailbox are also moved to the Purges folder. Items in this folder aren’t visible to users if they use the Recover Deleted Items tool. When the mailbox assistant processes the mailbox, items in the Purges folder are purged from the mailbox database. When you place the mailbox user on Litigation Hold, the mailbox assistant doesn’t purge items in this folder.

DiscoveryHold -> If a user is placed on an In-Place Hold, deleted items are moved to this folder. When the mailbox assistant processes the mailbox, it evaluates messages in this folder. Items matching the In-Place Hold query are retained until the hold period specified in the query. If no hold period is specified, items are held indefinitely or until the user is removed from the hold.

Versions -> When a user placed on In-Place Hold or Litigation Hold, mailbox items must be protected from tampering or modification by the user or a process. This is accomplished using a copy-on-write process. When a user or a process changes specific properties of a mailbox item, a copy of the original item is saved in the Versions folder before the change is committed. The process is repeated for subsequent changes. Items captured in the Versions folder are also indexed and returned in In-Place eDiscovery searches. After the hold is removed, copies in the Versions folder are removed by the Managed Folder Assistant.
********************

In Exchange Online, the default limits for the Recoverable Items quota are the same as Exchange 2016; a soft limit of 20 GB and a hard limit of 30 GB. However, the quotas for the Recoverable Items folder are automatically increased to 90 GB and 100 GB, respectively, when you place a mailbox on Litigation Hold or In-Place Hold.

When a mailbox is placed on one or more In-Place Holds and on Litigation Hold (without a duration period) at the same time, all items are held indefinitely or until the holds are removed.
In-Place Hold and Litigation Hold uses the Recoverable Items folder to preserve items.

Another possible scenario is the following:
 - the mailbox is not on Litigation Hold or part of an In-Place Hold Search; no Enabled Archive;
- as said above, by default the limits for the Recoverable Items are: a soft limit of 20 GB and a hard limit of 30 GB;
- you already have a large amount of data in Recoverable Items (15 GB -> 19 GB);
- you delete at once a large amount of data;
In this way you will hit the Recoverable Items limit.

There are 2 possible solutions for this case:

- Enable Litigation Hold for the mailbox (the quotas for the Recoverable Items folder are automatically increased to 90 GB and 100 GB). You can use the following command to verify the increase:
Get-Mailbox admin | FL Name,RecoverableItemsQuota,RecoverableItemsWarningQuota.
After the quota was increased, you can remove the Litigation Hold.
Example:
Get-Mailbox admin | FL Name,RecoverableItemsQuota,RecoverableItemsWarningQuota
Name: admin
RecoverableItemsQuota: 100 GB (107,374,182,400 bytes)
RecoverableItemsWarningQuota: 90 GB (96,636,764,160 bytes)

- Open a Service Request with Microsoft Support Team asking to increase Recoverable Items Quota.
********************
********************

You can find more detailed information about the Office 365 features used in this article, if you follow the links:

- Recoverable Items folder in Exchange 2016:
https://technet.microsoft.com/en-us/library/ee364755%28v=exchg.160%29.aspx?f=255&MSPPError=-2147217396
- Recover deleted items in Outlook for Windows:
 https://support.office.com/en-us/article/Recover-deleted-items-in-Outlook-for-Windows-49e81f3c-c8f4-4426-a0b9-c0fd751d48ce?ui=en-US&rs=en-US&ad=US
- Recover deleted items or email in OWA:
 https://support.office.com/en-us/article/Recover-deleted-items-or-email-in-Outlook-Web-App-c3d8fc15-eeef-4f1c-81df-e27964b7edd4?ui=en-US&rs=en-US&ad=US
- Retention limits across Office 365 options:
 https://technet.microsoft.com/en-us/library/exchange-online-limits.aspx#RetentionLimits
- Change how long permanently deleted items are kept for an Exchange Online mailbox:
 https://technet.microsoft.com/en-us/library/dn163584%28v=exchg.150%29.aspx?f=255&MSPPError=-2147217396
- In-Place Hold and Litigation Hold:
https://technet.microsoft.com/en-us/library/ff637980(v=exchg.150).aspx