We currently can't login in the Magento frontend with any browser except internet explorer.
even creating a new customer account and trying to log in with it did not work
we also cleared the Magento session cache and tried again
from comments in the question:
This was a browser cache/cookies related Problem.
Even clearing the Magento session cache did not resolve the Problem.
I assume that clearing the frontend cookie from the browser did the trick. This might have been an external module doing something with the frontend cookie.