Step 1) Run this query to create list of queries for each of the .Services tables.
-#QUERY--
select 'select * from '+s.name+'.'+t.name from sys.tables t join sys.schemas s on t.schema_id = s.schema_id where t.name = 'services'
#-----------

Step 2) Copy the results from step 1 into a new Query Window. Execute each line
individually (highlight a single line and press F5). Inspect the results of each line.
Verify each ServicHostId is a valid host in the environment. Current state 0 means that the machine is powered off. Note the Last Start time. You may see a ServiceHostID with all the fields filled with NULL.
In the below sample, OrchstrationSchema.Services table had a server that had been removed several years previously.

Step 3) For each .Service table, copy any rogue or invalid ServiceHostID out to Note Pad. Make a note of how many .Service tables have rogue or invalid ServiceHostID's. If all the .Services tables are correct, then stop, this is not the issue.
Step 4) Copy the below query to Notepad. Edit it by replacing the ServiceHostID with the one identified in Steps 2 & 3. The ServiceHostID should have single straight quotes surrounding. Paste the resulting script in a new query window and run it.
--------------Template script -------------Delete FROM ADIdentitySchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM HostingUnitServiceSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM DesktopUpdateManagerSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM Monitor.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM StorefrontSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM EnvTestServiceSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM ConfigurationSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM ConfigLoggingSiteSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM DAS.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM Analytics.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM AppLibrarySchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM OrchestrationSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'Delete FROM TrustSchema.Services WHERE ServiceHostId = 'ABB7747E-CC99-46D8-939B-793ED086841A'-------------end of script-------------Inspect the results. You would see (1 row affected) for each .Service table that had the invalid ServiceHostID in it. If the invalid ServiceHostID is not present in a .Service table, the result will be '(0 rows affected)'.

Step 5) To test that the database has the invalid ServiceHostId's removed, run each of the lines from Step 2 again and make sure that all the tables have only good Delivery Controllers listed.
Step 6) Make a new backup. Keep both backups (BEFORE and AFTER) for a few days until you are happy that all is well.
Step 7) Test adding the host connection.
IMPORTANT NOTE: If you are using mirror database or other HA configuration, make sure this procedure is executed on the PRIMARY database instance.
This procedure is safe to run on a production database.
Unimportant note: Use this query to find all the tables that have ServiceHostID. This article was created when ServiceHostID was only found in ".Services" tables.
SELECT c.name AS 'ColumnName' ,t.name AS 'TableName' FROM sys.columns c JOIN sys.tables t ON c.object_id = t.object_id WHERE c.name LIKE 'ServiceHostID' )
Problem Cause
Removal of a delivery controller was not complete and left an orphan ServiceHostID in some of the services.