In reply to the comment of @Andy David - MVP because the comment section is limited to 1000 characters:
No, a get-recipient doesn't throw an error. I have found only get-syncrequest and get-mailboxlocation cmdlets that fail but I haven't tried all other cmdlets in Exchange Online yet. Using the ObjectID may work as a workaround but doesn't solve the problem. Regarding support case: I have already opened one (#22032128) one month ago (still open) but I'm afraid they have no clue what's going on so I decided to post it here in the hope that a specialized engineer notices this issue. First they said it's because the user has not been migrated to Exchange Online yet. That was true but I can reproduce the issue even once the user has been migrated to Exchange Online. If this is a general issue I assume that this can be reproduced easily in any other environment with AAD Connect in place. Maybe someone can test it in his environment?
Steps to reproduce:
- Create a user on premise and sync it to AAD
- Remove the user from AAD: Remove-MsolUser -UserPrincipalName <upn>
- Remove the user from AAD recycle bin: Remove-MsolUser -UserPrincipalName <upn> -RemoveFromRecycleBin
- Force a sync or wait until next sync starts
- Use "Get-MailboxLocation -User <upn>" or "Get-SyncRequest -Mailbox <upn>" to get the error.