Microsoft Teams Direct Routing Outbound Calls not working (error 504)

Hello,

I am trying to configure Direct Routing on my tenant, using my carrier's hosted multi-tenant SBC.

They connected to my tenant with powershell and made all the needed configurations with these Powershell commands, after they validated the SBC domain in my office 365 tenant and created a user with that domain:

1. Set-CsOnlinePstnUsage -Identity Global -Usage @{Add ="TeamsVoice"}
2. New-CSOnlineVoiceRoute -Identity "DefaultRoute" -NumberPattern ".*" -OnlinePstnGatewayList <sbc fqdn> -Priority 1 -OnlinePstnUsages "TeamsVoice"
3. New-CsOnlineVoiceRoutingPolicy "VP-TeamsUser" -OnlinePstnUsages "TeamsVoice"
4. Set-CsUser -Identity user@domain.com -EnterpriseVoiceEnabled $true -HostedVoiceMail $true -OnPremLineURI tel:<phonenumber>
5. Grant-CsOnlineVoiceRoutingPolicy -Identity "user@domain.com" -PolicyName "VP-TeamsUser"

Don't need to add the SBC because of the multi-tenant config as specified in this article https://docs.microsoft.com/en-us/microsoftteams/direct-routing-sbc-multiple-tenants

Inbound calls are working correctly, but outbound calls are not.

My carrier's SBC is not receiving anything, and if I go to my PSTN direct routing report I get the SIP Error 504 "Unable to deliver INVITE: No such host is known" with the microsoft final code 569002.

My carrier believes it is a Microsoft Teams backend problem because they have other customers with the same config and they work properly.

What can I do? I also opened a ticket with Microsoft but I wanted to double up by also asking in here.

My user has got Office 365 E3 + Microsoft Phone System licenses and I have access to the number dial pad in the calls section of the app.

Thanks for the help