login problems with reauth=1

I noticed a lot of users requesting a change of their password and incidentally realized that the first login never works. you are alwayws redirected to mydomain.com/wp-login.php?redirect_to=http://mydomain.com/wp-admin/profile.php&reauth=1

the second login always works flawless. users are confused and keep requesting a password change

I have no idea when this started happening and what it might be related to. googling brings tons of results, anyone got a hint for me?

p.s. I tried deleting local temp files, cookies, different browsers and different computers, works all the same