Gracias. Ya lo solucioné. Le quité las cabeceras y le puse esto denbtro del bucle pero en la parte final en vez de al principio:
$de = "From: loque sea<
[email protected]>\r\n";
$de .= "Content-type: text/html; charset=UTF-8\r\n";
mail($para, $asunto, $cuerpo, $de);
Básicamente es lo mismo pero tal y como dices lo que influye es el orden a la hora de situarlo.
Muchas gracias por todo.
Un abrazo,