In attesa che il supporto di AVM mi risponda, ho fatto una prova: disattivando tutta la parte VoIP del Fritz!Box e spostando il NAT della porta 5060 verso un FreePBX su cui ho configurato un trunk con i parametri di Vodafone, tutto funziona perfettamente...
In più il Fritz non sembra avere questo problema con altri provider VoIP, p.es. ho provato con un numero di Clouditalia.
Quindi sembra che sia subentrata una qualche nuova incompatibilità tra Fritz e Vodafone... ma non, per esempio, tra Vodafone e FreePBX nè tra Fritz e altri carrier VoIP non Vodafone...