Yo tuve Ya.com con 4M/512k sin permanencia, y en mi contrato ponía que cobraban 25 € en concepto de baja, y me lo indicaron además durante la contratación.
Para darme de baja, les envié el ejemplo de baja que viene en la chincheta (Aquí), o una modificación del mismo, y lo envié por Burofax a la dirección que me dieron, y en la misma tarde ya aparecía en su panel de control como dado de baja, y en 2 días ya me dejaron sin ADSL, antes de que incluso terminara el mes que cobraban por prepago, pero no me cobraron los 25 € de la baja, y el bufete de Ya.com me envió una carta confirmando lo que solicité de la LOPD, y que el usuario había quedado bloqueado.
Un amigo mío la solicitó después por correo certificado, y tampoco le cobraron la baja. Creo que le tardaron cerca de 1 mes.
Después solicitó la baja de su 2ª adsl con Ya.com de igual forma (tenía 2 líneas a la vez en distintos sitios), y lo mismo, aunque le tardaron 2 meses.