Попробуйте воспользоваться вместо функции mail, напрямую на sendmail через сокеты :
$headers="To: $to\nFrom: $from\nSubject: $subject\n$headers";
$fp = fsockopen($server, 25, &$errno, &$errstr, 30);
if (!$fp)
die("Server $server. Connection failed: $errno, $errstr");
fputs($fp,"HELO $server\n");
fputs($fp,"MAIL FROM: $from\n");
fputs($fp,"RCPT TO: $to\n");
fputs($fp,"DATA\n");
fputs($fp,$headers."\n");
fputs($fp,$this->mime);
fputs($fp,"\n.\nQUIT\n");
while(!feof($fp))
$resp.=fgets($fp,1024);
fclose($fp);
в качетсве сервера используйте localhost или 127.0.0.1, если конечно на хостинге настроен sendmail.
Почитайте на
phpclub, там подробно все описано.