El problema no es la funcion mail si no la codificacion de caracteres, en las cabeceras deberias de agregar la linea:
Código PHP:
$mailheaders .= "charset=utf-8";
aunque por lo visto el mensaje no pasa por htmlentities() o utf8_encode(), se me hace raro.