Bien, luego de darme cabezazos contra la pared, he cambiado de hosting y el script ha funcionado. No como cabia esperar (headers, no envia el "from" ni el "subject"), pero ha funcionado. Al parecer, donde tenia alojado mi proyecto no permitia la funcion mail.
Quiza ayude a los que tengan un problema igual el incluir la funcion or die() tras la funcion mail(). Asi he podido saber si se enviaba y no llegaba (por motivo x) o directamente si no se enviaba. Eso es todo. Gracias por la ayuda.
Código PHP:
//funcion mail
mail("$email","$asunto","$cuerpo","$headers") or die ("Error al enviar");