Today I had the same issue as described above by Steve.
- The user provisioned from Google Workspace to EntraID was deleted in EntraID. After the redemption period it was deleted permanently, so not recoverable.
- Syncing this user freshly from Google Workspace wasn't working as I got the error '45010, Please restore this deleted user from Office 365 Admin Console.' However this user was not recoverable.
- Creating a new user in EntraID was not possible as you can't create new users with a domain that is federated.
What worked for me:
- Create a new user to replace the deleted user in EntraID that will use the UPN 'onmicrosoft.com' domain.
- Change the UPN and UnmuttableID using the Microsoft Graph Powershell Module to the federated domain.
- Connect-MgGraph -Scopes "User.ReadWrite.All", "Group.ReadWrite.All"
- Update-MgUser -UserId '<username>@<domain>.onmicrosoft.com' -UserPrincipalName '<username>@<federateddomain.com>' -OnPremisesImmutableId '<username>@<federateddomain.com>'
- After creating the user and setting the Immutable ID run the Sync in Google Workspace to sync the users. You see now that the other user properties like name etc. are synced.
- After that I could login again on office.com using the Google Workspace account.