Z.B. simyo macht das noch, allerdings ausdrücklich auf Kulanz (störungsfreier deutschlandweiter Empfang, unabhängig ob Wohnort oder nicht, könne nicht gewährleistet werden, "kein Empfang" sei nur u.U. Kündigungsgrund, wenn aufgrund Betreiberverschulden neu aufgetreten), in dem Fall bei Umzug Hamburg - norddeutsches Kaff.
Ich mach' das so ähnlich wie Rico; habe mir den einen billigen Tarif besorgt ohne Internet geholt, den ich b.B. billigstmöglich um eine vertragbindungsfreien Datentarif würde aufstocken können, habe ich dann auch nach ein paar Wochen gemacht (damals € 4,90 / 100 MB bei simyo, irgendwann mal kostenlos auf 200 MB oder so hochgestockt, ansonsten 9 ct pro SMS und Minute im Inland). Wenn man entweder sowieso nicht viel telefoniert und unterwegs nicht surft oder sich das Nutzungsverhalten erst noch herausstellen muss (was ich beim erstem Smartphone für recht wahrscheinlich halte) finde ich das auch die cleverste Variante, teurer und ggf. Vertragsbindung geht immer noch.