How to purge a soft deleted mailbox in Office 365

We have recently changed the way, removing an Office 365 user with attached mailbox, behaves.

Previously:
If we deleted an active user while he was still licensed, his mailbox would go into a “soft deleted” state and could have been recovered, just by restoring the user.
If we also purged the MsolUser from Office 365 with “Remove-MsolUser -ObjectID <guid of soft deleted user> -RemoveFromRecycleBin -Force”, his soft deleted mailbox would also be purged, unless it was specifically put on Litigation Hold or In-Place Hold.

Currently:
The first situation remains the same, as in if we soft delete the user account, while he still has a license assigned, his mailbox will go into a soft deleted state.
The change however, is that if we purge the user account, the mailbox is no longer purged with it, instead it will remain in a soft deleted state, regardless if previously it was put on Litigation Hold/In-Place hold or not.

Now, this post is all about how to purge a soft deleted mailbox (or how to reconnect it when you no longer have the original MsolUser account).
We have observed different error message that are encountered during a migration to Office 365, because we are trying to move a mailbox in Office 365, that was previously soft deleted for certain reasons (initial migration failure, etc), and we still have that soft deleted object, but we just don’t know about it, because of the previous behavior known with purging users in Office 365 (i.e. once the user was purged, his mailbox would go away as well).
In this situation, we might need to purge the soft deleted mailbox, but we may also encounter some error messages while trying to do so.
First, let’s discuss about how a mailbox reaches the “soft deleted” state:

1. We delete the user associated with the mailbox from the Office 365 Admin Center/Active Users interface (license must not be removed before deleting the user). At this point, the mailbox is soft deleted.

2. We then use PowerShell, to purge the user from Office 365:

- Get-MsolUser -ReturnDeletedUsers | fl UserPrincipalName,ObjectID
- Remove-MsolUser -ObjectID <guid from previous command output> -RemoveFromRecycleBin -Force

3. The mailbox will still be in soft deleted, and can be checked either in Exchange Admin Center/Recipients/Mailboxes/More/Deleted Mailboxes and in PowerShell with the command Get-Mailbox -SoftDeletedMailbox user@domain.com

4. We should notice the fact that if we run Get-Mailbox -SoftDeletedMailbox user@domain.com | fl ExternalDirectoryObjectID, we no longer have a value on this parameter, as the MsolUser associated with this mailbox, has been previously purged, so basically the mailbox is now orphan.
How can we reconnect this mailbox to another user:

We can use the procedures mentioned in this article https://technet.microsoft.com/en-us/library/dn894100(v=exchg.150).aspx

What if I need to urgently purge the soft deleted mailbox:

The same article as above can be used, and PowerShell will be your best friend in this situation, but as mentioned earlier in this post, we may have some errors when trying to purge it:

- The operation couldn't be performed because 'Soft Deleted Objects\Mailbox1' matches multiple entries – another mailbox is active with the same details.

- The operation couldn't be performed because there is a soft deleted user; please remove the soft deleted user and then try again – there is an active user with the same details.
- The operation couldn't be performed because it is outside the writing scope of this server - the soft deleted mailbox has the “IsDirSynced” flag set to True.

- The "Disconnect" parameter can't be used on the "Remove-Mailbox" cmdlet because it isn't present in the role definition for the current user. Check the management roles assigned to you, and try again. – for this you might need to contact Microsoft Support as this means there might be an issue with RBAC permissions. This error message can be encountered as well when trying to purge multiple mailboxes at once, as removing one by one seems to do the trick.

The above error messages are not 100% accurate, but we should be able to purge any soft deleted mailbox, by first reconnecting it to a fictional user.
Instructions on how we can connect Powershell to Exchange Online, can be found here: https://technet.microsoft.com/en-us/library/jj984289(v=exchg.160).aspx
Instructions on how we can connect Powershell to Office 365 (on all services in one session), can be found here: https://technet.microsoft.com/en-us/library/dn568015.aspx

1. Run this command in Powershell: New-Mailbox -InactiveMailbox <address of soft deleted mailbox or guid> -Name <new unique name> -MicrosoftOnlineServicesID <a new unique UPN> and then press enter in order to go ahead and provide a password for the new user mailbox that will get created. Do not attempt to use the parameter UserPrincipalName as you will receive an error message saying that you do not have permission to use it, stick with MicrosoftOnlineServicesID instead.

2. If all went well, we should see a yellow warning message that tells us to assign a license in 30 days.

3. Run Get-Mailbox -SoftDeletedMailbox to make sure the mailbox is no longer there.

4. After all this we can try again to purge the new mailbox:

- Soft delete the new user in Office 365 Admin Center
- Hard delete the MSOL User with Powershell (Remove-MsolUser -ObjectID <guid> -RemoveFromRecycleBin -Force)
- Check soft deleted mailboxes and purge it with Get-Mailbox -SoftDeletedMailbox <new address> | Remove-Mailbox -PermanentlyDelete
NOTES:
Beware of the difference between these commands:
- New-Mailbox -InactiveMailbox (used to reconnect mailboxes to other users than the initial account to which the mailbox was associated; the command will also remove the mailbox from a soft deleted state and will make it active)

- Undo-SoftDeletedMailbox (this is used to reconnect the soft deleted mailbox, if we still have the initial user to which the mailbox was previously associated, in the tenant; this command also removes the mailbox from a soft deleted state and will make it active)

- New-MailboxRestoreRequest (this command will be used if we want to restore the content of a soft deleted mailbox into a new active mailbox; the command will NOT remove the mailbox from its soft deleted state)

- We may also encounter this error message when trying to reconnect the mailbox: The parameters passed to the cmdlet represent a managed account, which doesn't match the namespace state, which is federated. – this means that we are trying to use a MicrosoftOnlineServicesID that has a federated domain (we should instead use the onmicrosoft.com domain)

- This entire procedure can be used similarly for soft deleted Public Folder Mailboxes that need to be purged:

Get-Mailbox -PublicFolder -SoftDeletedMailbox <name of the PF Mailbox> | Remove-Mailbox -PublicFolder -PermanentlyDelete
IMPORTANT:
If we have any soft deleted mailboxes on Litigation Hold or In-Place Hold, these must be removed in order to purge them:

Get-Mailbox -InactiveMailboxOnly | fl Identity,LitigationHoldEnabled,InPlaceHolds

Get-Mailbox -SoftDeletedMailbox | fl Identity,LitigationHoldEnabled,InPlaceHolds

Set-Mailbox -InactiveMailbox user@domain.com -LitigationHoldEnabled $False

For mailboxes that have InplaceHolds parameter populated we must look for the e-Discovery that was previously used to search and put on hold the content of those mailboxes. Once we have found the correct e-Discovery search, we must edit it and remove those mailboxes from the “Source” or “Mailboxes to be searched” area. This will clear the InPlaceHolds flag.
More details about Litigation Hold and In-Place Hold, can be found here:
https://technet.microsoft.com/en-us/library/dn743673(v=exchg.160).aspx  - Litigation Hold
https://technet.microsoft.com/en-us/library/dd979797(v=exchg.150).aspx  - In-Place Hold
Please be advised that this post, does not apply to hard deleted mailboxes, or mailboxes that got deleted by removing the Exchange license from the user. Removing the license is equivalent to Disable-Mailbox, and if the user is also deleted afterwards, the mailbox can no longer be recovered and is also not viewable with below 2 commands. Support can't help in this scenario.
We are able to manipulate mailboxes that can be seen with either one of these 2 commands in Powershell:
Get-Mailbox -SoftDeletedMailbox
Get-Mailbox -InactiveMailboxOnly
Useful articles:
https://technet.microsoft.com/en-us/library/aa997663(v=exchg.160).aspx
https://technet.microsoft.com/en-us/library/jj200770(v=exchg.160).aspx
https://technet.microsoft.com/en-us/library/ff829875(v=exchg.160).aspx