I know there are a lot of solutions posted here, but nothing seems to work for me.
$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);
And the message comes like "Slaptaþodþio prisiminimas" (þ instead of ž) in subject and "Paspauskite �i� nuorod�, kad pasikeistum�te slapta�od�: nuoroda" instead of other Lithuanian letters in the message body.