Я знаю, что здесь опубликовано множество решений, но мне кажется, что ничего не работает.
$headers = 'From: '.$HOST_EMAIL."\r\n" .
'Reply-To: ' .$HOST_EMAIL. "\r\n" .
'X-Mailer: PHP/' . phpversion() . "\r\n" .
'MIME-Version: 1.0' . "\r\n" .
'Content-type: text/html; charset=utf-8' . "\r\n".
'Content-Transfer-Encoding: 8bit';
mail($to, '=?UTF-8?B?'.base64_encode($subject).'?=', $body, $headers);
И сообщение приходит как "Slaptaþodþio prisiminimas" (þ вместо ž) в теме и "Paspauskite �i� nuorod�, kad pasikeistum�te slapta�od�: nuoroda "вместо других литовских букв в теле сообщения.