Du kannst je nach Anzahl halt mit "Suchen & Ersetzen" oder mit schlichtem Kopieren und Einfügen manuell in einer Tabelle arbeiten. Beides geht ja bei Thunderbird nicht so einfach, da du ja jedes Mal das Fenster des Kontaktes wechseln musst.
Angenommen, du hast 1000 Kontakte: Alle z.B. exportieren als csv und mit z.B. Excel öffnen. Dann eine Spalte vor den z.B. privaten Telefonnummern einfügen und mit +49 füllen (durch Kopieren & Einfügen, bis alle 1000 voll sind). Danach hinter der Spalte mit den Telefonnummern die Zellen "verketten" lassen (und auch wieder kopieren & einfügen, bis alle 1000 Zeilen voll sind), so dass in der neuen Spalte die Nummern so stehen: +490123456789, Dann noch mit Suchen & Ersetzen auf einen Schlag die überflüssige Null entfernen und die anderen beiden nun unnötigen Spalten löschen.
Sollte zügig machbar sein, denke ich.