Exakt, war der Fehler. Allerdings kann man trotz hoher Internetaffinität, oder gerade wegen dieser, Fehler dieser Art begehen. Ich konnte einfach nicht ahnen, dass man wirklich den QR-Code für spätere Zwecke speichern muss. Warnungen dergleichen waren anscheinend auch zu gering und mit meiner Erwartungshaltung ging ich davon aus, dass man sich darauf verlassen kann, wie auch bei Google Auth über Gmail.
Leider musste ich dann feststellen, dass das gute System bei Gmail noch nicht für Smartphones verfügbar ist und man tatsächlich einfach "Pech" hat, wenn die Software - warum auch immer - abschmiert.
Ein anderer Thread hier impliziert, dass es nicht zwangsweise online sein muss. Auf der Passwort vergessen Seite ist aber leider nur dieser Weg. Vermutlich muss mir jemand vom Support die Daten dafür geben, aber da reagiert keiner.
edit: Den FAQ Eintrag habe ich gelesen. Wie vermutlich jeder, NACHDEM er ein Problem hat.