Tildes en mail según el servidor destino

[PosProdukcion]

Hola, estoy enviando mails desde mi sitio, alojado en dinahosting, y en función de como lo programo me sale bien en según que correos, por ejemplo:

Esta versión la veo bien en mi mail de 1&1 o de gmail pero no veo las tildes en yahoo ni hotmail, bueno, en hotmail lo veo bien en web mail pero mal al leerlo desde thunderbird.

Código PHP:

$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/plain; charset=utf-8\r\n";
$headers .= "From: Colecciones <[email protected]>\r\n";
$headers .= "Reply-to: Colecciones  <[email protected]>\r\n";
 
mail($pemail, "Tu pedido de la colección", $contenido_mail, $headers);
 

Esta otra versión, la veo bien en hotmail o 1&1 pero mal en yahoo:

Código PHP:

$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/plain; charset=utf-8\r\n";
$headers .= "From: Colecciones  <[email protected]>\r\n";
$headers .= "Reply-to: Colecciones  <[email protected]>\r\n";
 
mail($pemail,utf8_decode("Tu pedido de la colección"), utf8_decode($contenido_mail), $headers);
 

Además, 1&1 no muestra el "From" (muestra un guión) y en el cuerpo del mail muestra un montón de cabeceras (esto no lo hace con otros correos), mientras que el resto si muestran el "From" y no muestran cabeceras dentro del mail.

¿Alguien me puede ayudar? Codificar con ISO-8859-1 no ayuda, ¿será cuestión de la configuración del SMTP?

Gracias