Office 365 Mailbox of unlicensed user

(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.

Issue had to do with the fact that even though the user was created in office 365, it didn't have a corresponding exchange mailbox. By creating a mailbox for this Office 365 user the migration succeeded.