@danchily The problem seems to be that you sent the cancellation to the wrong address (included it woth the rental hardware instead of sending it to Erfurt) - and therefor it was never received by Vodafone. But it is (or better was) your obligation to send the cancellation to the right address (and also get proof of receival).... Any lawyer will tell you exactly the same thing (plus he'll take your money for this answer) - and won't do anything else.
Same applies to any other contact method except the official ways. And keep in mind that you must have already provided proof of movement to Vodafone - if you haven't done yet, even an earlier cancellation that would have been received by Vodafone could not have been processed...
Sole contractual language is German - if you send letters in English, they may be simply rejected - especially if sending them to the wrong address.
And the other thing:
Even despite the language fact - your letter did not include all the necessary information needed for this kind of cancellation. It missed at least the confirmation of your movement (e.g. the "Abmeldebestätigung")...
