There can be situation where you need completely remove an re-create your Hybrid configuration which can seem challenging from required actions point of view. Procedure below describe steps needed to be done in order if you want remove and create Hybrid Configuration for example if you receiving following error when running Hybrid Configuration Wizard:

Execution of the Set-FederatedOrganizationIdentifier cmdlet has thrown an exception. This may indicate invalid parameters in your hybrid configuration settings.
 Federation trust "yourfederateddomain/Configuration/Deleted Objects/Microsoft Federation Gateway DEL:xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx" wasn't found. Make sure you have typed it correctly.
 at Microsoft.Exchange.Management.Hybrid.RemotePowershellSession.RunCommand(String cmdlet, SessionParameters parameters, Boolean ignoreNotFoundErrors)

That particular procedure is written for Exchange 2013/Office 365 Wave 15 configuration, but it works pretty well for Exchange 2010/Wave 15 Hybrid.

Clean-up

1. Execute following command on you on-premise Exchange 2013 server (that command is not available on Exchange 2010, if your Hybrid server is Exchange 2010, just skip that step):

   Remove-HybridConfiguration

2. Remove existing organization relationships from both on-premise and O365 (you can use that command, if you have just single relationship on each side):

   Get-OrganizationRelationship | Remove-OrganizationRelationship

3. Remove Federation Trust using ADSIEdit:
   1. Start ADSIEdit, connect to Configuration Partition, expand CN=Configuration,DC=your,DC=domain, expand CN=Services, expand CN=Microsoft Exchange, expand CN=yourexchangeorg, double-click CN=Federation Trusts
   2. In right-hand pane select CN=Microsoft Federation Gateway, right-click on it and select Delete

Create new Federation Trust

1. First run following command on on-premise Hybrid server:

   Get-ExchangeCertificate | where {($_.CertificateDomains -eq 'Federation') -and ($_.Status -eq 'Valid')} | Select-Object -Expand Thumbprint

2. You will see one or more strings with numbers and letters (for example: FFFFFFC752C0EDB0BF70CF6C9E241B0DC246292), pick one (any) copy and paste it to some text file.

 

3. Run following command:

   New-FederationTrust -Name "Microsoft Federation Gateway" -Thumbprint <thumbprint>

   where <thumbprint> is string  you copied in previous step.

4. Then run following command on on-premise Hybrid server:

    Get-FederatedDomainProof –DomainName yourdomain.com

   After execution command from step 3 you will see DNS record that you should add to Public DNS (it will look like yourdomain.com TXT IN long_hash_number).

   You will need to add that record in to public DNS. Please note that sometime it take up to 24 hours to pick up changes.

   You may receive same hash that already present in DNS. It will happen if you will use same certificate for trust. Then make no changes, just proceed with next step.

5. Execute following command on on-premise Hybrid server:

   Set-FederatedOrganizationIdentifier –AccountNamespace <some_domain> –DelegationFederationTrust “Microsoft Federation Gateway”

   In that step please use any domain that is already present in Accepted Domains in your organization, but not domain you going to federate. You will receive error saying “Proof of ownership has failed.”

   It is expected, that will refresh Org ID.

Create new Hybrid Configuration

1. Run following command on on-premise Hybrid server:

   Set-FederatedOrganizationIdentifier –AccountNamespace yourdomain.com –DelegationFederationTrust “Microsoft Federation Gateway”

2. Run following command on on-premise Hybrid server:

   Get-FederationInformation -DomainName yourtenantdomain.onmicrosoft.com | New-OrganizationRelationship -Name "OnPremise_toO365" –FreeBusyAccessEnabled $true -FreeBusyAccessLevel LimitedDetails

3. Run following command on O365 tenant:

   Get-FederationInformation -DomainName yourdomain.com | New-OrganizationRelationship -Name "O365_toOnPremise" –FreeBusyAccessEnabled $true -FreeBusyAccessLevel LimitedDetails

4. Run Hybrid Configuration Wizard from on-premise Exchange 2013 ECP

Now your Hybrid configuration should be working again.