My customer has three public facing domains that is required as part of the Exchange Online migration. I've added them into Verified Domain in Office 365 portal, ran HCW v3, added the TXT records required for Microsoft Federation Gateway, and when I clicked on "Verify TXT record" button, all 3 domain changed into "TXT record found", and the first domain proceed to be stuck at "Adding federated domain".
Looking into the HCW log (always a good place to start with %appdata%\Roaming\Microsoft\Exchange Hybrid Configuration\), the following error was found:
2017.04.20 01:08:12.023 *ERROR* [Client=UX, Page=DomainProof, Thread=17] Microsoft.Online.CSE.Hybrid.Provider.PowerShell.PowerShellInvokeException: PowerShell failed to invoke 'Set-FederatedOrganizationIdentifier': Unable to reserve domain "FYDIBOHF25SPDLT.company.com" for Application Identifier "000000004C04A704". Detailed information: "A Windows Live ID error occurred. Detailed information: "PassportError: Passport error.".". ---> System.Management.Automation.RemoteException: Unable to reserve domain "FYDIBOHF25SPDLT.company.com" for Application Identifier "000000004C04A704". Detailed information: "A Windows Live ID error occurred. Detailed information: "PassportError: Passport error.".".
--- End of inner exception stack trace ---
at Microsoft.Online.CSE.Hybrid.PowerShell.RemotePowershellSession.RunCommandInternal(Cmdlet cmdlet, SessionParameters parameters, Int32 millisecondsTimeout, PowerShellRetrySettings retrySettings, Boolean skipCmdletLogging)
at Microsoft.Online.CSE.Hybrid.Session.PowerShellOnPremisesSession.SetFederatedOrganizationIdentifier(SmtpDomain accountNamespace, String delegationTrustLink, SmtpDomain defaultDomain)
at Microsoft.Online.CSE.Hybrid.App.ViewModel.Pages.DomainProof.DomainInfo.AddFederatedDomain(IOnPremisesSession session, AppData appData)
at System.Collections.Generic.List`1.ForEach(Action`1 action)
at Microsoft.Online.CSE.Hybrid.App.ViewModel.Pages.DomainProof.VerifyActivity(IOnPremisesSession session, IEnvironment environment)
Restarting HCW did not help.
Resolution: Verify one domain at a time. In the page "Select the domains that you want to be part of your Hybrid Configuration", pick only one domain, and click Next, and proceed to verify that domain. Using the Back button, go back and pick another one (and unselecting the previous one) and verify that domain, and repeat for the last domain.
Hope this helps someone.