Convert AD connect synced user to shared mailbox

(NOTE: Microsoft is constantly updating the feature sets of Exchange Online. This information may become dated but was accurate in the fall of 2014. If you notice any differences with the way MS is handling mailboxes of a deleted user as you read this please leave a comment and I will update the answer.)

What options do we have at this point to get the mailbox restored?

I'll only cover the options within the scope of the administrative options of Office 365 itself. If you have 3rd party offerings or solutions in place you'll need to contact them for assistance.

First, we have to determine if the deleted mailbox still falls within the retention period.

For Office 365, this period is 30 days by default from mailbox deletion date. After 30 days, the mailbox is permanently deleted and is not recoverable. If you are within this retention period you can follow this Technet article for steps on restoring the mailbox: Delete or Restore User Mailboxes in Exchange Online .

If you are outside the retention period, you cannot recover the deleted mailbox...UNLESS you have enabled a feature Microsoft refers to as Inactive Mailboxes. This is accomplished by having the mailbox on either Litigation Hold or In-Place Hold prior to deleting the mailbox.

Manage inactive mailboxes in Exchange Online states:

Exchange Online makes it possible for you to preserve the contents of deleted mailboxes indefinitely. This feature is called inactive mailboxes. A mailbox becomes inactive when an In-Place Hold or a Litigation Hold is placed on the mailbox before the corresponding Office 365 user account is deleted. The contents of an inactive mailbox are preserved indefinitely. This allows administrators, compliance officers, or records managers to use the In-Place eDiscovery feature in Exchange Online to access and search the contents of an inactive mailbox. Inactive mailboxes can't receive email and aren't displayed in your organization's shared address book or other lists.

IMPORTANT: Make sure the hold is in place BEFORE deleting the mailbox. Personally, I recommend you setup all of your mailboxes with Litigation Hold (instead of In-Place Hold) when you create their accounts to begin with. This allows full recovery of any mailbox item at any time which is beneficial with deleted items after a year, etc.

If the mailbox falls into the category of an Inactive Mailbox then you can recover items in those mailboxes by one of two ways.

Option #1 - In-Place E-Discovery

After you make a mailbox inactive by placing the mailbox on hold and then deleting the corresponding Office 365 user account, you can access the contents of the inactive mailbox by using In-Place eDiscovery in the Exchange admin center (EAC). When you search an inactive mailbox, you can create a keyword search query to search for specific items or you can return the entire contents of the inactive mailbox. You can preview the search results, copy the search results to a discovery mailbox, or export the search results to an Outlook Data (PST) file.

Option #2 - Restore entire mailbox

Inside the Exchange admin portal, choose the ellipse and then choose Deleted Mailboxes:

Then you'll see a list of recoverable Inactive Mailboxes along with their deletion date. You can select the mailbox and choose Recover:

After you select Recover you'll get a new Window. You'll need to change to `Deleted Mailbox Unique Information" and set a Login Name and password for the mailbox account at that point. Then you can click Recover.

After the mailbox is recovered you can either login to it via OWA with the account, or just give your admin account Full Access to it and then let it create that extra profile in your existing Outlook (after about 30 minutes, just restart Outlook if it is Outlook 2013).

SO...my recommendation is to place every mailbox you have on either Litigation Hold or if your Legal/Compliance puts a restriction on something so permanent, at least an In-Place hold before deleting a mailbox/user in Office 365, especially if they are an employee that sends/receives business critical emails or sensitive information.

Oh man, what a mess, lets see.

The process of restoring a mailbox depends on how the mailboxes was originally deleted:

• Mailbox deleted by means of removing the Exchange License: applying an Exchange license to the user would simply reactivate the mailbox in this case, here is the correct way to do that.
• Mailbox deleted by means of deleting the original user account: recreating the user account in this case with the same mailbox ID/SMTP proxy settings will force Exchange to restore the mailbox to the user. here is the correct way to do that.

If none of those options worked, then I'd recommend you to complete delete the mailbox even from Recycle Bin and start all fresh, as follow:

1. If the user is DirSynced/Federated, start by removing the user mapping so the mailbox is not connected to an Active Directory account.
2. If the mailbox has a user account online, delete that account too.
3. In Office 365 Admin Portal > Users > Deleted Users, verify that you can see the mailbox you want to fix (if it's not in the deleted users tap, it's still linked to an account then, verify user mapping and remove as needed)
4. Connect Powershell to Office 365: https://msdn.microsoft.com/en-us/library/dn975125.aspx
5. Delete the mailbox from Recycle Bin using this command:

Remove-MsolUser -UserPrincipalName "Username" -Force -RemoveFromRecycleBin

6. Recreate the user account/mailbox as needed.

Hope this helps.