Do your users have access to the microflow that you specified on the deeplink configuration?
The login page that appears when you're not logged in is not the default mendix login page. It is a specially crafted page that makes sure that when you log in, you are sent back to the deeplink to attempt access again. This should work when you use the built-in mendix authentication mechanisms. Custom SSO or authentication mechanisms might break this, depending on how they are implemented.
Are you using a different authentication mechanism, such as LDAP, Kerberos or mendix cloud authentication? Can you test whether logging in works when you use default authentication instead of that?
Just wanted to chime in on this question. I have noticed there is an issue with the DeepLink module that refuses a login with correct credentials after a user has successfully logged into the application and then signs out. I was planning to create a ticket for this issue and deliver a test project with it today. It is reproducible behavior. This issue is not present in Mendix 4 and earlier versions and started to occur in Mendix 5. The only way to make logging in using a DeepLink to work again is to quit your browser and restart it, or open a (new) incognito (Chrome) or private (Firefox) window and open the deeplink again.