Got a bit further with investigating this problem.

1: I found out the session handler for the admin section is defined through the includes/functions/sessions.php and NOT through the expected admin/includes/functions/sessions.php. Dunno if this makes any difference to the working of the admin section.

2: I can log in if I change the admin from DB-based sessions to file-based sessions. So it certainly has something to do with the session handler. However the shop itself works fine with the DB-based sessions.

For anybody needing a quick workaround: try changing the sessions to file based sessions!