You want to set up a hybrid deployment between your on-premises Exchange Server organization and an external federated organization. However, when you run the Set-FederatedOrganizationIdentifier cmdlet, the operation isn't successful, and you receive an "InternalError InternalError: Internal error" error message. The full text of the message resembles the following:
Execution of the Set-FederatedOrganizationIdentifier cmdlet had thrown an exception. This may indicate invalid parameters in your Hybrid Configuration settings. An error occurred while attempting to provision Exchange to the Partner STS. Detailed Information "An unexpected result was received from Windows Live. Detailed information: "InternalError InternalError: Internal error.".". at Microsoft.Exchange.Management.Hybrid.RemotePowershellSession.RunCommand(String cmdlet, Dictionary`2 parameters, Boolean ignoreNotFoundErrors)'.
This problem occurs if the domain name for your organization was previously in use and you try to reconfigure the domain. A domain name may be blocked in Windows Live for the Azure Active Directory (Azure AD) authentication system if the domain name was previously used.
To resolve this problem, contact Microsoft Support, and reference this Knowledge Base article.
Microsoft Exchange Online, Microsoft Exchange Server 2013 Enterprise, Microsoft Exchange Server 2013 Standard Edition, Microsoft Exchange Server 2010 Enterprise, Microsoft Exchange Server 2010 Standard