The Scenario
A customer moving mailboxes from 2003 to 2010 to Office 365 over a weekend. All mailboxes moved from 2003 to 2010 without an issue. However, moving mailboxes to the cloud proven a bit more troublesome. Several mailboxes failed with this error:

So what we have here is the object in the cloud does not have all the prerequisite email addresses required for a move of On-Prem to Office 365. Where does this object exist and how can we see what Office 365 has stamped it with? In the ‘GUI’ or Office 365 Portal, simply login, go to the Exchange portion of the portal and location Mail Contacts in the Recipients section:


From here, search for the troublesome object. Click on the Edit button and click on ‘Email Addresses’ and review what is configured for the object:

If you try to add one like suggested by Microsoft in this article and you have a hybrid environment, you will receive an error about the object being synched with AD thus changes cannot be made here.
What about in PowerShell? Can we check out the email addresses here as well? Sure. Just need a simple two line script:
$email = (Get-MailUser [mailbox alias]).emailaddresses foreach ($line in $email) {$line}
The reason you would do this instead of something that would seem easier like this:
Get-MailUser [mailbox alias] |fl emailaddresses
.. is that the output for the second command can be incomplete if there are a lot of email address. What do I mean by incomplete? Consider a user account with 6 email addresses. If I run the second command I get output like this:
Notice the trailing dots at the end implying that there are more email addresses to be shown. If we run the first command we get a complete list of email addresses:
The Solution
Since our environment is a hybrid environment, we need to make corrections/additions in the OnPrem Active Directory. To add an email address for a mailbox, you can either do ADSIEdit, Exchange Management Console or PowerShell. The easiest for a one off is the Exchange Management console. Simply go to the console, Recipient configuration –> Mailbox, find the user, double-click on the user and then click on the E-Mail Addresses tab. Add the email address here. After this step has been completed, you can either force a sync via the ‘Start-OnlineCoexistenceSync’ PowerShell command on your DirSync server or wait until the normal background sync happens for Office 365.
The Result
Once the sync has completed we can now verify the address is present:
$email = (Get-MailUser [mailbox alias]).emailaddresses foreach ($line in $email) {$line}
The results should now show the additional email address:
Now the mailbox will migrate to the cloud with all the other mailboxes.
Thanks alot