А вообще можно так попробывать:
В коде по умолчанию стоит конвертация в кодировку koi:
PHP код:
$body=convert_cyr_string (stripslashes($body),w,k);
$subject=convert_cyr_string (stripslashes($subject),w,k);
$sucess = mail($mailto, $subject, $body,
"From: $email
X-Mailer: PHP/" . phpversion());
Код не мой.