remote move request not an accepted domain for your organization

So you've got your fancy Hybrid configuration all set up between your on-premise Exch 2010 SP3 server(s) and the office 365 cloud and you only get this error on some mailboxes.  Your dirsync is working fine, and your ADFS is even working for once.  Depending on your situation you may even have noticed that it's mostly older user mailboxes that are giving you grief.  In my case we used to have other domain names in use and when those were decommissioned, the extra Email addresses were never removed from the mailboxes.  For the Remote move to work, the only email address domains that can be attached to that mailbox have to be listed under the Domains tab in the office 365 admin page.  Once you remove the extras, then wait a while, then force a Dirsync, then wait a while and try again it'll go through.

Example:

UserA has these email addresses:
usera@contoso.com
usera@contoso.mail.onmicrosoft.com

UserB has these email addresses:
userb@contoso.com
userb@contoso.mail.onmicrosoft.com
userb@notcontoso.net

If the domains tab in office 365 only has contoso.com and contoso.mail.onmicrosoft.com, then UserA will move but UserB will fail.