Кодировка может? с названием темы были проблемы.
Ещё когда в $То неправильно писал типа "абвгде фыва _my(a)domen.ru_", и когда перечислял адреса не через зпт.
У меня так шлёт (не жемэйл, правда)
$additional_headers = "From: $from" .PHP_EOL
."Content-type: text/html; charset=$win1251" .PHP_EOL
."Reply-To: $ReplyTo" .PHP_EOL
.'X-Mailer: PHP/' . phpversion();
// На случай, если какая-то строка письма длиннее 70 символов, используем wordwrap()
$result= mail ($to,
mb_convert_encoding( $subject, $win1251, $win1251),
wordwrap( mb_convert_encoding( $message, $win1251, $win1251)),
mb_convert_encoding( $additional_headers, $win1251, $win1251) ); // Wind <--- UTF