This issue is caused by an ExchangeGUID mismatch between your on prem and Azure AD user objects. It is easily resolved using PowerShell. In my example it was because the ExchangeGUID in the cloud was not the same as the one for the on prem mailbox. I knew the hybrid and EWS was functioning correctly as it was allowing me to migrate certain mailboxes, it was only some users that would fail with this error.
Open the Exchange Management Shell from the on prem server and run the following command to find out what the on prem Exchange GUID is.
Get-Mailbox <MailboxName> | Format-List ExchangeGUID
Now run the following command from an Exchange Online session. To do this follow instructions in the following post http://blog.ryanbetts.co.uk/2016/08/creating-sessions-to-exchange-online.html
Get-MailUser -Identity <UserName> | fl displayname,ExchangeGuid
As you can see in my example the Exchange GUID's are in fact different.
From the Exchange Online session use the following command to manually set the GUID to match the on prem one.
Set-MailUser -Identity firstname.lastname@example.org -ExchangeGUID 9f2xxxa3b-xxxxxxxxx57d4dxxx3a1
Once this command completes you can use the Get-MailUser command again to check the changes have been written to Azure AD.