For users who run into the same problem:
Newly registered users could not log in via the widget, the error message said that credentials were wrong. After long searching I think I found the solution: I am using W3 Total Cache with caching of database queries. Adding "user" to the "Reject query words" in the Database Cache settings seems to fix it.
Object cache doesn't seem to be a problem.