Da das angeführte Problem bei manchen immer noch/mal wieder aufkommt (die letzten 2 Wochen alleine 3 mal über ehem. Kunden), die das oben beschriebene Problem hatten, hier der Vollständigkeit halber noch ergänzend, dass ein falsch gesetztes Domain Cookie ebenfalls verhindern kann sich erfolgreich anzumelden.
Im Backend:
System => Konfiguration => Site => Cookies => Domaincookie