Teams can not chat with email user

Our company just joined Office365. We are using Teams - but we can not chat with external users.

When entering a user email - we get the

* a popup - "Search mailto:abc@def.com externally"

* The response is "We did not find any match"

As far as I checked, we have External Access Guest allowed in our Admin.

Any idea?

Thanks