Otros detalles a tener en cuenta:
http://www.php.net/manual/en/function.mail.php
Por ejemplo el hecho de separar las cabeceras por un \n\r es lo que recomiendan .. pero si no funcionan dice ahí mismo que uses \n
Cita: additional_headers (optional)
String to be inserted at the end of the email header.
This is typically used to add extra headers (From, Cc, and Bcc). Multiple extra headers should be separated with a CRLF (\r\n).
Note: If messages are not received, try using a LF (\n) only. Some poor quality Unix mail transfer agents replace LF by CRLF automatically (which leads to doubling CR if CRLF is used). This should be a last resort, as it does not comply with RFC 2822.
Un saludo,