So, vielen Dank für die Tipps. Ich bin ein wenig weiter gekommen - leider klappts aber noch nicht.
Ich habe von Vodafone einen Benutzernamen und ein Passwort bekommen.
Die Einstellungen in der Fritzbox habe ich nach den Angaben aus diesem Forum gemacht:
http://www.dsl-forum.de/vodafone_rou...en_t16134.html

VPA/VCI: 0/33
UBR with PCR
Peak Cell Rate: 700

PPPoE, LLC/SNAP Bridging

PPP username: wie auf Vodafone anmeldung:
usario: BlaBla@vodafone
contrasenja: BlaBlaBla <-- richtiges pw eintragen
enable NAT

enable WAN Services
wobei in der Fritzbox VPI & VCI steht. Nehme an das entspricht dem VPA / VCI und "PPPoE, LLC/SNAP Bridging" nennt sich in der Fritzbox nur PPoE oder PPPoA / LLC .

Leider klappt es dennoch nicht. Mein Verdacht sind immer noch die Benutzerdaten.
Mein Benutzername sieht wie folgt aus: VFAU0123456789 (also 4 Grosßbuchstaben und dann 10 Ziffern)
Das Passwort besteht aus 8 Zeichen. (Großbuchstaben und Ziffern gemischt)

Auch wenn ich den Benutzernamen mit @vodafone oder @VODAFONE ergänze führt noch kein Weg ins Netz.
Kann mir ein Vodafonekunde bestätigen, dass insbesondere der Benutzername, bei ihm ziemlich ähnlich aussieht und wie es sich mit Groß- und Kleinschreibung usw. verhält?

Fröhlicher Gruss

Wolfgang