Federated chat does not work

I have problem with my O365 tenant; federated chat does not work.

My tenant has both cloud users and AD synchronized users. I have double-checked related settings, and I can confirm that Teams should allow external messages. I have also asked the system administrator to check Firefall and DNS settings. Fiddler trace does not reveal immediately recognizable errors.

Symptoms: Cloud users (x.onmicrosoft.com) may search and find external users on other tenants. Presence status works. However, teams fail to deliver chat messages with an error: "We ran into a problem sending this message. Try again later." User with a cloud account is also able to initiate an audio call. Unfortunately, the recipient (external O365 tenant) will not see the alarm. Curiously recipient does see a notification about a failed audio call.

I can confirm this behavior with a test tenant. The account in my test tenant can chat with other O365 tenants. He is *not* able to find an external cloud-only user who is a member of the problematic tenant. That user can, however, find my test account as an external user but cannot chat with it because of the error described above.

My test account can find users with a custom domain that get synced from the local Active Directory server. There are no errors with chat messages, but I was not able to validate if the recipient ever received my test message.

Any ideas?