External Identities / Cross-tenant log-in error (Selected user account does not exist in tenant 'xyz' and cannot access the application 'uuid' in that tenant. The account needs to be added as an external user in the tenant first.)

Question

Hello,

I'm the admin of two (test) Entra ID tenants. One of the tenants, lets call it MAIN has a single tenant application registered. All my users can log in and access this app. I would like to also allow users from a different tenant, lets call it PARTNER to access my application.

At the moment users form the PARTNER tenant get the following error after log-in:
Selected user account does not exist in tenant 'xyz' and cannot access the application 'uuid' in that tenant. The account needs to be added as an external user in the tenant first. Please use a different account.

What do I have to change/configure that users from the PARTNER tenant can access may app?
Limitations:

• I cannot change the application, it supports only a single tenant because of library limitations.
• The PARTNER tenant will have thousands of users, inviting all of them is not feasible.

Update:
When I invite a user from the PARTNER tenant it works. Do I need a license with "Cross-tenant synchronization" to get it working without manual invitation?