SOLUCIONADO, el problema era el doble cambio de línea en los encabezados, dejando sólo el \n y sin ningún encode() se soluciona en todos los servidores de destino que he probado:
Código PHP:
Ver original$headers = "MIME-Version: 1.0\n";
$headers .= "Content-type: text/plain; charset=utf-8\n";
mail($pemail, "Tu pedido de la colección", $contenido_mail, $headers);
La solución, vista en los comentarios de
esta página (lo SOLUCIÓN está en el comentario de Martin, el resto del artículo no vale para esto).
Saludos