If you happen to find yourself in the situation where you have un-licensed an Office365 user from Exchange Online then restoring in can be a few simple steps. You can un-license a user by checking the Exchange Online.
There are warnings about un-licensing the user will delete the data but maybe you thought it was a different user. You could also have had a script go rogue and accidently remove the license from a bunch of users.
If you know who the users that had their mailboxes deleted then you can easily re-license them. If not you'll need to figure out the users that have deleted mailboxes. I've been told that Get-RemovedMailbox should show you this information but I can't seem to replicate those results in my tenant.
You can try these commands to view the mailboxes.
1. Connect to Exchange Online with PowerShell, detailed in TechNet article.
$Session = New-PSSession-ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell/-Credential $Cred-Authentication Basic-AllowRedirection
2. Run the Get-RemovedMailbox command
This lists all of the recently removed mailboxes.
Once you have the AD accounts you can then just use the Admin Portal to check the Exchange Online license option. You may have to wait up to 24 hours for the full mail data to return but in my testing they seems to come back in a matter of minutes. You can validate that the mailbox has returned by opening the mailbox with the "Open another mailbox..." feature which you can find when you have an email account open in Outlook Web Access.
If you get the "something went wrong" page, it just means you don't have permissions to view it. Global Admins for the tenant do not have rights to view others' mailboxes by default, it must be granted.
This KB article ( http://support.microsoft.com/kb/2685435 ) tells how to grant access to all mailboxes. You can use this PowerShell command to grant access to a specific mailbox.
Get-Mailbox -Identity email@example.com |Add-MailboxPermission -User firstname.lastname@example.org -AccessRights fullaccess -InheritanceType all
You can then validate the permission change with PowerShell as well.
Get-MailboxPermission -Identity email@example.com | Select-Object User, AccessRights, Deny, IsInherited
Now you will be able to open the Mailbox to view that it has been successfully restored.