Nochmal ganz allgemein und nicht auf den Einzelfall bezogen:
Verträge sind dazu da eingehalten zu werden - von beiden Parteien. Und das weiß man vor Abschluss von langfristigen Verträgen. Mindestvertragslaufzeiten haben den netten Effekt, dass dann die Konditionen für den Kunden besser sind - die Kosten müssen sich ja nur über den gesamten Zeitraum amortisieren. Von daher ist es i.d.R. unangemessen verlangen zu wollen, dass ein Vertrag vorzeitig gekündigt wird. Der Vetragspartner ist schließlich nicht verantwortlich für Änderungen im Lebenswandel des anderen. Inwieweit es Ausnahmen gibt, hängt u.a. auch davon ab, ob es generell nur Angebote mit MVLZ gab - auch von anderen Anbietern - und somit die Alternative fehlte.
In der Realität gibt es aber sehr oft einvernehmliche Lösungen, die die Kosten für den Kunden zwar nicht auf Null bringen, aber zumindest gering halten. Insbesondere dann, wenn der Vertragspartner weiß, dass er durch die Vertragsauflösung nicht nur entgangene Einnahmen hat, sondern auch Einsparungen hätte, die er gegenrechnen kann. Im Fall von DSL-Anschlüssen wären das die Mietkosten für die letzte Meile, etwaige Kosten für Datenmengen und wenn eine Telefonflat enthalten ist, Telefonkosten. Dazu ist es aber nötig, dass der Vertragspartner in der Lage ist, mit seinen Kunden zu kommunizieren - im Zeitalter der Hotline ist das meist das schwierigste.
Wenn daher das Gespräch mit dem Vetragspartner nichts bringt, ist kompetenter rechtlicher Beistand gefragt (Verbraucherzentrale, Anwalt). Irgendwelche Tips hier im Forum, das eine oder andere Rechtsmittel anzuwenden, Formulierungen von Schreiben, usw. würde ich tunlichst überlesen. Jeder Einzelfall ist anders. Und was sinnvoll ist und was nicht, hängt schließlich auch von der Summe ab, um die es geht. (Und wenn es ein berufsbedingter Umzug ist, ist es zumindest den Versuch wert, die Restkosten des Vetrages von der Steuer absetzen zu wollen. Auch das drückt die Last.) Eventuell ist ein Streit mit dem Vertragspartner gar nicht mehr lukrativ - besonders wenn man den Aufwand und weitere Kosten noch rechnet. Aber auch das kann nur ein Anwalt vernünftig im Hinblick auf den zu erwartenden Erfolg abschätzen.
Und das ist mitnichten eine Rechtberatung, sondern meine Meinung, was Veträge wert sind und wie man sich verhalten könnte.