Welcome to the Auth0 Community!
Could you please let me know if in your logs the Failed Verification appears first or the Successful Verification?
By any chance, do you test this with users creating in the dashboard or with users which signed up?
The issue might be caused by the fact that an user created within the dashboard have an empty value for {{ application.callback_origin }} resulting in an invalid redirect_url. You can read more about that in this community post.
Also, this issue could be caused by multiple requests. Did you by any chance click the link multiple times when verifying the new mail?
Alternatively, if you are using an email template, you can attempt to delete the Redirect To attribute.
You can also double check if the email instance you are testing with automatically click the user’s link for them or if they are using click tracking. This can be an issue specifically with Office 365. You can check if you receive the Successful Verification message prior to clicking the link. You can try using an email client which does not send the email to the end-user inbox such as mailtrap.io.
Let me know if the information above was helpful or if you have any other questions regarding the matter!
Kind Regards,
Nik