[ IMPORTANT UPDATE March 2015: Microsoft deprecated the procedure for moving mailboxes from one user to another which was described in this post and also removed the get-removedmailbox Powershell cmdlet on which it depended.
The current approach to this seems to be built around the New-RestoreMailboxRequest powershell cmdlet, where the idea is that you take the mailbox that was deleted from user A and restore its content to a mailbox for user B.
Microsoft’s current blog post discussing this topic can be found here.
The text that was originally on this page has been deleted because following those directions with today’s Exchange Online environment would result in data loss. I have it on my to-do list to do some experimentation and document how to do this using today’s tools. ]