Digging through the database, it turned out that affected accounts had thousands of auth tokens in the oc_authtoken table. Based on an old reply on another thread, having many of these slows down the login process vastly.
I have deleted tokens of these users, and authentication is fast again.