Sodele,
problem gelöst.
Es war eine APP "IProtect", welche "Le Cheffe" installiert hatte und sich nicht mehr dran erinnert hat. Iprotect schickt eine SMS an die hinterlegte Rufnummer wenn das Telefon neu gestartet wird oder eine andere SIM-Karte eingelegt wird. Dabei war die Rufnummer in dieser APP als "0172xxxxxxx" hinterlegt. IProtect hat nun schlauerweise einfach draus "000172xxxxxx" gemacht.
Vodafone selber scheint im Billing-System nun folgenden Algorithmus zu haben:
Wenn Rufnummer mit + anfängt, kappe +-Zeichen
Wenn Rufnummer mit 00 anfängt, kappe 00
Wenn Rufnummer nur 0 am Anfang hat, kappe 0 und füge 49 hinzu.
Das führt dann dazu, das normale SMS immer mit 49 oder andere landesvorwahl im EVN stehen.
Wenn eine dumme App nun an 00-0172xxxxx eine SMS schickt, wird die 00 gekappt und im EVN steht nicht 49172xxxx sondern 0172xxxx und da eine 00 gekappt wurde und das ganze auch sonst irgendwie nicht zuordnebar ist, wird halt ne kostenpflichtige SMS mit 19c abgerechnet 
Für die Google-Leser die auch SMS berechnet bekommen, obwohl sie eine SMS Flatrate haben: Einfach mal schauen, ob nicht doch irgendeine APP dumm programmiert ist.
Im Zweifelsfall Gerät komplett flashen und neu installieren und bei jeder APP drauf achten ob nicht doch irgendwo eine Rufnummer eingetragen wird.
Seit dem "Cheffe" 49172xxxxxx in Iprotect eingetragen hat, bekommt er jetzt brav die SMS und berechnet werden die auch nicht 
Gruss und danke! an Linea für die doch wirklich seeeehr kompetente Hilfe Vodafone-Intern!
Wolfgang