Hola, a mi me funciono añadiendo al header la siguente linea:
Código PHP:
$mailheaders .= "Content-type: text/html; charset=utf-8\r\n";
Con esto me salen las ñ y los acentos áéíóú, de forma correcta tanto en mayúsculas como en minúsculas.
A ver si te funciona... creo que no en todos los servidores funciona, pero a mi de momento no me ha vuelto a dar problemas.