Acentuação no mail

Olá

Estou fazendo um envio de email em php com a função mail.

Coloco o cabeçalho em UTF-8, mas mesmo assim em alguns emails funciona e em outros os acentos horríveis.

$toAddress = "meu email";
$assunto = "teste";
$msg = "áéíóúãç<br>teste";

$headers = "MIME-Version: 1.0" . "\r\n";
$headers .= "Content-type: text/html; charset=utf-8" . "\r\n";
$headers .= "From: nome <email>";

mail($toAddress,$assunto,$message,$headers);

Coloquei na mensagem o utf8_decode, aí nesses webmails que nao estavam funcionando, funcionam, mas nos que estavam não funciona. Ou seja, inverte o problema.

Alguém pode me ajudar?

Obrigada

Luka.