Cloud Voicemail will not connect after setting up Hybrid mode for Skype for Business 2019

Question

i have followed the guidance to setting up Hybrid mode to allow access to Cloud Voicemail for my Skype for Business on-premises users. When trying to call a users voicemail I am getting a fast busy.

Logs are showing:

ms-diagnostics: 1008;reason="Unable to resolve DNS SRV record";source="FE1@mydomain.com";dialplan="Hosted__exap.um.outlook.com__mydomain.onmicrosoft.com";umserver="exap.um.outlook.com";responsecode="504";msexchdomain="mydomain.com";msexchdns-srv-result="NegativeResult";msexchdns-source="InternalCache";msexchsource="sip.mydomain.com";appName="ExumRouting"

Server: ExumRouting/7.0.0.0

What am I missing? I can find no documentation for configuration on the M365 side. Everything i have read says the Skype for Business users are setup automatically for mailbox use.

Anyone out there setup this configuration? Exchange 2016 / Skype for Business 2019