Contrato de permanencia telefonía móvil

En agosto del 2012 acepte una oferta de un terminal a cambio de 6 meses de permanencia. No firme contrato pues fue a través del móvil. Hace unos días me robaron el teléfono y me puse en contacto con la compañía, en este caso vodafone, para que me dijeran como actuar. El agente que me atendió me dijo que tenia que bloquear el móvil, cosa que hice en el momento, y que debía enviarles un fax para solicitar la retirada de la permanencia, cosa que me extraño pues yo pensaba que ya había finalizado, junto a la fotocopia del dni y la denuncia presentada en la policía. Una vez enviado el fax me debía de poner en contacto con ellos pasadas 24 h para hacer el tramite. En una primera llamada me atiende un agente y me dice que han recibido el fax (lo puse desde una oficina de vodafone con acuse de recibo) que van a realizar la retirada de la permanencia pues según ellos no era de seis meses sino de 24, y me hacen una oferta para enviarme otro terminal sin coste pero ampliando la permanencia a 24 meses mas. Como tengo varios números de teléfono en el mismo contrato le pregunto si puede ser que la permanencia me la haga en otro de los números y ademas cambiando a una tarifa de datos. Me dice que si es posible y me da varios terminales a elegir a coste 0, como le comento que me gustaría verlos físicamente me dice que me puedo pasar por cualquier tienda vodafone y verlos, que al dar mi dni ya les saldrá a ellos que esta oferta corresponde al robo del móvil y que me va a pasar con el departamento de bajas para que me gestionen la retirada de la permanencia y ahí empiezan los problemas. No me retiran la permanencia que según ellos tengo hasta agosto del 2014, no me ofrecen ningún móvil a coste cero, no me pueden hacer la permanencia nueva en otro numero, no les ha llegado el fax, tenia que haber llamado en 72h, me cobran 230€ de penalización... Después de muchas llamadas, muchos agentes, muchos departamentos en el que cada uno me dice una cosa diferente y llegan a tratarme de deficiente mental no he podido llegar a ningún acuerdo . Mi pregunta es ¿es legal el contrato de permanencia que hice telefónicamente? ¿La penalización que me piden es la que corresponde? Tenia entendido que como máximo son 150€ ¿qué ocurre si hago portabilidad a otra empresa y doy orden en el banco de no atender los recibos de vodafone? ¿Hay alguna manera de obligarles a que cumplan lo que me dijo el primer y el segundo agente ya que se supone que graban las conversaciones?