Tienes una buena ensalada con respecto a los "separadores" de las cabeceras HTTP .. en algunas usas un \n y otras \r\n .. o no las usas en todas.
Dependiendo del S.O. del servidor que envie ese e-mail (el MTA que uses bajo PHP) y de quien lo reciba .. así serán interpretadas esas cabeceras. Si no interpreta bien un "salto de línea" ("separador" como es \n .. o \r\n) no interpretará esa cabecera como independiente que debe ser sino como algo como lo que observas.
Revisa la documentación oficial de mail() Y observaciones al respecto:
http://www.php.net/manual/en/function.mail.php
Fijate en los ejemplos .. usa \r\n como "salo de línea" .. también ten presente el orden de las cabeceras (que no sé si "altera el producto") pero por si a caso .. (no me he leido las RFC's correspondientes al protocolo SMTP) ..
Un saludo,