One of the most common error message I find when performing mailbox moves to Office 365 – Exchange Online is the “MigrationPermanentException: The target mailbox doesn't have an SMTP proxy matching 'company.mail.onmicrosoft.com'.” error:
The error message is pretty descriptive and is caused when the mailbox being moved doesn’t have a proxy address that matches the routing domain. In an Exchange hybrid deployment, the hybrid configuration wizard updates the on-premises email address policies to ensure that all mailboxes have the relevant SMTP proxy address added. This should work fine except in instances when for whatever reason a mailbox or group of mailboxes are not being updated by an email address policy. Typically because the “Automatically update email addresses based on the email address policy applied to this recipient” has been manually removed:
There are a couple of ways to fix this, you could just enable the email address policy for those particular mailboxes, but the risk with that option is that it may have been removed for a particular reason. Email address policies are additive only, so while an email address policy will not remove or overwrite an email address, it may change the default SMTP address.
Or, you may want to simply add the relevant SMTP proxy address for those mailboxes, this can easily be done via PowerShell. I have published a PowerShell script to simplify this process, check it out on the TechNet Gallery.