Wenn du die Nummer verifizieren kannst, dann müsste es auch mit der Übermittlung durch die FritzBox klappen. Früher hieß es immer, man müsste die Nummer mit der 0049 verifizieren. Wenn das nicht mehr geht, und du die +49 nehmen musst, dann probier es trotzdem mit der 0049 in der FritzBox. Bei webcalldirect konnte ich meine Festnetznummer auch ohne internationale Vorwahl verifizieren. Also einfach Vorwahl+Rufnummer. Das könntest du auch noch probieren.
Dann unbedingt "Internetrufnummer für die Anmeldung verwenden" anhaken.