Handy nur durch dreimal PUK zu öffnen. Pin unbekannt

Hallo,
ich hatte vor einiger Zeit aus Versehen dreimal die falsche PIN eingegeben. Dann mit PUK wieder entsperrt und auf Anfrage meines Handys die alte Pin geändert. Wie auch immer es dann passiert ist: ich glaube ich habe wohl nochmal die falsche Pin eingegeben, weil ich an die alte dachte. Dann wieder mit PUK entsperrt, allerdings musste ich die PUK dreimal eingeben. Diesmal wurde ich nicht nach einer neuen PIN gefragt, allerdings funktioniert auch die alte nicht mehr. D.h. wenn ich das Handy runterfahre, muss ich immer mit dreimal PUK entsperren. Dann ist zwar alles in ORdnung, aber es ist ja doch etwas ungut, wenn man gar nichts mehr für den Notfall hat. Und die lange PUK ist auch schnell mal falsch eigegeben, wenn es Alltag ist und man es immer drei mal machen muss.
Die Frage ist also: wie kann ich eine neue PIN generieren, ohne die alte zu kennen? Bei Telefonica / Fonic sagten sie mir, es sei unmöglich, dass man drei mal die PUK eingeben muss. Ist aber so. Eine Lösung wäre nur eine neue SIM-Karte. Bevor ich das mache, hoffe ich jetzt abe rnochmal auf Expertenwissen.
BIn gespannt!
Ella