As a consultant in messaging and collaboration I have created dozens of Exchange hybrid configurations that last years, ranging from Exchange 2010 to Exchange 2019.
Today we’ve run into an issue I have not seen before, the HCW8001 – Unable to determine the Tenant Routing Domain error:

Note. In one of my earlier blogs Moving from Exchange 2010 to Office 365 somebody mentioned this specific error in the comments in September 2018.

When you click Learn more you are redirected to the following Microsoft page:
https://support.microsoft.com/en-us/help/3068010/unable-to-determine-the-routing-domain-for-the-cloud-organization-erro which states you have to enable Directory Synchronization using the following command:

Set-MsolDirSyncEnabled -EnableDirsync $true

Which of course we did, but no success.

Azure AD Connect was running fine, I checked the configuration (optional features) and found nothing strange and no errors were logged.

When checking the Microsoft Portal I could see Directory Synchronization was running:

The tenant routing domain is typically something like <tenantname>.mail.onmicrosoft.com and this is set in Office 365 when installing Azure AD Connect. But when checking the Accepted Domains (in Exchange Online) this domain is not available:

There’s no way you can add this <tenantname>.mail.onmicrosoft.com domain manually (also not via the Microsoft Online Portal) so you are out of luck (I tried the Azure AD Connect server multiple times, but it didn’t work).

You can open a ticket with Microsoft Support or see if you can create a new tenant and start over again. Since this happens rarely I would be surprised you run into this again with a new tenant.