Joaol , wish I had found this sooner because I think I have narrowed it down to this bit:
Step 1: Verify that the URL for the on-premises Exchange REST API has been published on the public network
Run https://docs.microsoft.com/en-us/microsoftteams/troubleshoot/known-issues/teams-exchange-interaction-issue#common-troubleshooting-steps in the Common Troubleshooting Steps above against the user's mailbox to locate the on-premises Exchange EWS URL, and change the URL format (replace "/EWS/Exchange.asmx" with "/api") in this manner: https://mail.contoso.com/EWS/Exchange.asmx to https://mail.contoso.com/api.
Try to access the REST API URL from a browser in the external network. If you get a 401 response from the on-premises Exchange environment, the REST API URL has been published. Otherwise, contact the local network team to get the URL published.
In my test network I get a 401 response and a prompt for a username and password but in my live network I do not.
Now I did not configure the network for either of these environments but I must admit, the following phrase "Otherwise, contact the local network team to get the URL published." is pretty vague? Do we need to do anything in IIS?
KevinCallanan yeah, checked and it is TeamsOnly.
Many thanks,
Dan