Have you checked for any potential conflicts/duplicate values? If you are certain the address is not in use, you can use one of the following workarounds:
- Change the user UPN to user@tenant .onmicrosoft.com. As Microsoft enforces a requirement that at least one SMTP address should match the UPN, this will solve the issue. You can change the UPN back to the original value after.
- Use the -WindowsEmailAddress parameter, which allows you to change the primary SMTP address even for synced users. For example: Set-Mailbox user@keyman .com -WindowsEmailAddress user@tenant .onmicrosoft.com
You can change it back to the original value after.