Самое простое решение, если вы не возражаете против кодирования даже слов, которые ему не нужны, - это поместить все в кодированное слово base64 RFC 2047:
$subject= "=?utf-8?b?".base64_encode($subject)."?=";
$body= "blah blah $utf8text blah";
$headers= "MIME-Version: 1.0\r\n";
$headers.= "From: =?utf-8?b?".base64_encode($fromname)."?= <$fromaddress>\r\n";
$headers.= "Content-Type: text/plain;charset=utf-8";
mail($toaddress, $subject, $body, $headers);