Alice macht nicht "heimlich" VoIP. Auf deren Webseite finden sich alle Infos. In Bereichen, die nicht an die eigene Vermittelungstechnik angeschlossen sind, werden die Sprachedaten über eine spezielle Datenverbindung getunnelt.
Allgemein kommt es aber doch gar nicht darauf an, in welcher Form der Anbieter die Gespräche weiterleitet, sondern was der Anschluss kann. Wenn ein Anschluss versprochen wird, der mit einem Analog- oder ISDN-Anschluss kompatibel ist und in der Leistungsbeschreibung oder AGB keine Einschränkungen gemacht werden bzw. nur diese Einschränkungen nicht funktionieren, gibt es überhaupt keinen Grund eine vorzeitige Kündigung zu verlangen.
Und wenn Du Dir z.B. die Versatel-Seite mal anschaust, dort ist der Leistungsumfang sehr genau spezifiziert.