По стандарту в заголовках письма должны использоваться только символы из основного ASCII-набора (0x00-0x7F). Все остальные символы должны быть закодированы.
Если письмо содержит HTML-часть, то крайне желательно добавить соответствующую по тексту PLAIN-часть. Тип письма должен быть multipart/alternative.
При несоблюдении этих условий резко возрастает вероятность попадания письма в спам.
Кодировку лучше использовать UTF-8, как наиболее универсальную.
$fromName = "=?UTF-8?B?" . base64_encode($fromName) . "?=";
$toName = "=?UTF-8?B?" . base64_encode($toName) . "?=";
$subject = "=?UTF-8?B?" . base64_encode($subject) . "?=";
$boundary = md5(rand());
$headers = "From: {$fromName} <${fromEmail}>\r\n".
"MIME-Version: 1.0\r\n" .
"Content-type: multipart/alternative; boundary={$boundary}\r\n";
$message = "\r\n--{$boundary}\r\n" .
"Content-Type: text/plain; charset=UTF-8\r\n\r\n" .
$plainMessage .
"\r\n--{$boundary}\r\n" .
"Content-Type: text/html; charset=UTF-8\r\n\r\n" .
$htmlMessage .
"\r\n--{$boundary}--\r\n";
mail("{$toName} <{$toEmail}>", $subject, $message, $headers);