Io a questo punto immagino che Vodafone abbia fatto qualche modifica lato server che va in conflitto con la gestione della sessione SIP di AVM (se AVM non ha fatto aggiornamenti di recente).
I Fritz hanno possibilità di configurazione VoIP piuttosto limitate, quindi non c'è molto da provare - si può provare ad abilitare o disabilitare le poche opzione presenti, e vedere se cambia qualcosa.
Per capirci di più bisognerebbe confrontare una sessione SIP fatta con il Fritz e una fatta con la VS o altro sistema che funziona, e vedere cosa c'è di differente. Ma temo che sia qualcosa che deve sistemare AVM con un aggiornamento.