Hybrid Configuration Wizard - DataStrings.InvalidSmtpDomainName(domain) error connecting to On-Premise Exchange

I recently ran into an issue with a customer who was running the new Hybrid Configuration Wizard (https://aka.ms/taphcw), where the tool was unable to connect to the Exchange On-Premise environment, with the error DataStrings.InvalidSmtpDomainName(domain).

The underlining cause was configuration data remaining from a decommissioned Exchange server, within the Exchange configuration in Active Directory. Once this configuration was removed the Hybrid Configuration Wizard ran and completed successfully.

This issue resulted in the support article https://support.microsoft.com/en-us/kb/3132123 so any future occurrences of this issue can be quickly resolved. The article contains the in-depth steps needed to remove the configuration for the (decommissioned) On-Premise Exchange server.