ну не знаю... дело в том, что на ТОМ же хостинге другой программер знакомый пишет так:
mail($EMAILTO,$EMAILSUBJ,$MESSAGE,\'From: \'.$EMAILFROM."\\nReply-To:
".$EMAILREPLYTO."\\nX-Mailer: PHP/".phpversion());
Письма приходят нормально. Найди десять отличий называется