During an ongoing Office 365 deployment, we identified an issue with Office 365 customers not being able to change a user’s UPN if both UPN’s are in federated domains. We have identified and validated a work-around, please see the guidance below. Thanks to Dmitry Kazantsev for help in the write-up, this has also been posted on the Office 365 Community Wiki.
Therefore for us to provide customers with UPN rename functionality we will have to engineer some sort of the provisioning process that will provide two-step rename via a standard (non-federated domain). The steps below illustrate such process with a use-case scenario with the fictitious company Contoso. We will assume that Contoso has a default standard (non-federated) domain of contoso.onmicrosoft.com and contoso1.com and contoso2.com both of which are federated domains, and that Contoso is running Directory Sync: