When you decommission an Exchange Server in your Organization and have a Hybrid Configuration, one of the things that does not occur is that the server is not removed from the Hybrid Configuration (msExchCoexistenceRelationship) to reflect this. When you run the Hybrid Configuration Wizard, after the decommission, you'll see the following error:

The wizard did not complete successfully. Please see the list below for error details.
Exchange server "<Server>" was not found. Please make sure you typed the name correctly.

 

Given the above, you'll see something similar to the following in Exchange Management Shell for the Hybrid Configuration:

SendingTransportServers   : {UNDERJORDISKE
                            DEL:416ba20c-62c1-4a28-95e5-8dbb6430dc96, LJUSALFER
                            DEL:89bf8a7d-144f-43b8-8aee-b8ac6f98721f}

 

One method to resolve this issue is to do a modification of the object in Active Directory. Using ADSIEdit, browse to the configuration container and either go to the object's path (Config container > Services > Microsoft Exchange > Organization Name > Hybrid Configuration) or just create a new query (objectClass=msExchCoexistenceRelationship). Once you have the object, look for the property you want to fix (in this case, it was 'msExchCoexistenceTransportServers'). I removed the two defunct values.

I, then, used Exchange Management Shell to get the DistinguishedName of the current Transport Servers in the Organization:

Get-TransportService | FL DistinguishedName

DistinguishedName : CN=HYLDA,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=minvan,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=minvan,DC=se
DistinguishedName : CN=STROMKARLEN,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=minvan,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=minvan,DC=se

I copied these values into the same property I removed the defunct values, previously. After doing so, I re-ran the Hybrid Configuration Wizard.