I assume these users are using SPInitiated flow where users goes to application URL and gets redirected to your tenant. I also assumed, these users are already log in into their AAD and hence either have PRT/MSISAuth cookies etc., which they present to your AAD. Since these users are not present in your tenant, you get the above message.
Is the text of the message is your concerns? Well, that is absolutely inaccurate and misleading. However, the behavior is 100% expected.
In case you want to allow access to applications registered in your tenant, you need to use B2B. Add these users as guest into your tenant so that your tenant can issue token.
Your application only trust token issued by your tenant.