@Christian Kuhr , are the trace logs at %ProgramData%\Microsoft\Azure AD Connect Authentication Agent\Trace
providing any information? I would check here if you haven't already.
You could also try with PowerShell to test the Pass-through Authentication agent:
Import-Module "C:\Program Files\Microsoft Azure AD Connect Authentication Agent\Modules\PassthroughAuthPSModule\PassthroughAuthPSModule.psd1"
Invoke-PassthroughAuthOnPremLogonTroubleshooter
Enter the same username and password that are used to sign in to https://login.microsoftonline.com
.
You said you recreated the user account, but try checking the UserPrincipalName (UPN). Make sure that the user's on-premises UPN matches the user's cloud UPN. A mismatch can cause sign-in issues.
Please let me know your results and I can help you further.
Best,
James