ผมก็เคยเจอปัญหานี้นะครับ ตอนที่ลองใช้ class ที่โหลด มาจาก www.phpclass.org

function sendmail($from, $to, $subject, $message)
 {
  if($message)
  {
   $subject = "=?utf-8?B?".base64_encode($subject)."?="; //  หัวข้ออีเมล์
   $headers = "MIME-Version: 1.0\r\n";
   $headers .= "Content-Type: text/html; charset=utf-8 \r\n"; // encoding
   $headers .= "From: ".$from." \r\n";
   
   return mail($to, $subject, $message, $headers);
  }  
 }

ตัวอย่างการเรียกใช้
sendmail($from, $to, $subject, $message);

ผมใช้แล้วไม่มีปัญหาอะไรเลยครับ ลองเอาไปใช้ดูครับ