Recently I had a need to restore a Deleted User/Mailbox in Office 365 for one of my clients. With the recent Soft Delete being implemented, I figured this should be very easy. Unfortunately it was not, I first tried to just restore the mailbox to a new user as the original problem was related to the user account in Office 365. I found this article, http://technet.microsoft.com/en-ca/exchangelabshelp/ee423634 which talks about using the variations of RemovedMailbox cmdlets. This failed miserably! Either there is an issue with the clients tenant or that this article is out of date as I was never able even to find the deleted mailbox, much less restore it.
I ended up opening a support request with Microsoft Online services and received the proper information I needed. The tech with MSOL Support pointed me to this article, http://support.microsoft.com/kb/2619308 and using the PowerShell command for restoring an account with a ProxyAddress conflict worked great. The reason I had a ProxyAddress conflict was because to get this affected user back up and running I created a temporary user and added the email addresses to it. I am still unsure and need to research more about doing a strict mailbox restore without restoring the user account, but the 2619308 KB was very helpful and should be bookmarked for any Office 365 administrator. I also found this Help Topic that discusses doing the restore via the Office 365 Portal, http://onlinehelp.microsoft.com/en-us/office365-smallbusinesses/hh534382.aspx#BKMK_2.