Hallo!
a) Wie schon meine Vorgänger erwähnten wird ein Vertrag, der im Shop abgeschlossen wird, mit der Akzeptierung des Netzbetreibers wirksam (im Normalfall sofort nach positiver Bonitätsprüfung).
Ein Vertrag setzt 2 Willenserklärungen voraus: Deine Willenserklärung durch die Unterschrift unter dem Vertrag, der Netzbetreiber durch die Akzeptierung über das jeweilige Freischaltsystem.
Bei bestimmten Geschäften gibts es Ausnahmen (Haustür- Internet- oder Telefonverträge), hier hat man 14 Tage Widerrufsrecht.
b) Mangelnde Netzabdeckung ist keinesfalls ein Grund dafür einen Vertrag vorzeitig zu beenden, die meisten Netzbetreiber haben dies sogar in ihren AGB's vermerkt!
Zumal es in Deinem Fall auch nur mangelnde UMTS-Netzabdeckung ist, GSM wird ja vermutlich vorhanden sein?!
Aber wie schon gesagt, selbst daß wäre kein Kündigungsgrund, hier hättest Du Dich eben vorher informieren müssen.
c) Der Mitarbeiter bei Vodafone hat Deine Kündigung nicht angenommen, für Dich ärgerlich aber durchaus nachvollziehbar.
Ich arbeite auch in einem Handy-Shop und würde niemals eine Kündigung annehmen oder bestätigen!
Warum?
Überleg Dir mal den Fall, Du bestätigst eine Kündigung mit Datum und Unterschrift und leitest die per Fax an den Netzbeteiber weiter.
Aus Umständen, die Du nicht kontrollieren kannst (Faxserver-Ausfall, technischer Fehler etc.) kommt die Kündigung nicht oder nicht rechtzeitig an.
Was würdest der Kunde für einen Terror machen, Dir die Schuld geben, womöglich Anwalt einschalten und einen Rechtsstreit anfangen etc.
Und glaub mir, den Streß würdest auch Du Dir nicht antun wollen, soviel verdient man nicht als einfacher VB 
d) Einschreiben ist nicht zwingend erforderlich, einfach die Kündigung per Fax oder per Post an den Netzbetreiber schicken (die Kundenbtreuung von Vodafone ist meines Wissens in Ratingen, irgendwas mit Seestern?) und um eine Bestätigung bitten.
Vodafaone wird Dir dann ganz regulär die Bestätigung schicken daß die Kündigung nach Ablauf der 24 Monate Mindestlaufzeit wirksam wird...
edit: Ich war zu langsam, das meiste hat mein Vorgänger schon beantwortet 