This is an error I came across recently that had me stumped. In my case this happened when I attempted to email a user via an external email address. Usually when this occurs it would be a wrong proxy address or they haven’t got a remote mailbox set up. This one was a little different however, when doing the Get-RemoteMailbox command on the Exchange 2010 Management Shell I could see that they did in fact have a remote mailbox. Digging a little deeper I then thought I should check that the Exchange GUID of the on-premise object to see if it matches the online one; Low and behold it didn’t!
To fix this you will need to join the on-premise mailbox to the online object. In order to see how to do this please check out the following blog.
Hope this helps!