Tenta:
<?php header('Content-type: text/html; charset=UTF-8');
$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/html; charset=UTF-8\r\n";
$headers .= "From: email@exemplo.com\r\n";
$headers .= "Reply-To: email@exemplo.com\r\n";
$mensagem = 'mensagem';
$assunto = 'assunto';
mail($email_do_user, $assunto, $mensagem, $headers);
?>
Se usares o Notepad++, grava em UTF-8 without Bom e tem que estar a funcionar. Não te esqueças de definir o próprio HTML como UTF8.