Esto error parte de la configuración del idioma del sitio de correos que recibe el mensaje, no porque ellos estén mal, sino porque seguramente la codificación de la página de correos (está en unas de las etiqueta META de la página, creo) no reconoce los acentos o caracteres especiales latinos.
Por otra parte, podrías especificar que tu mensaje será HTML (no sólo Texto), y así podrías pasar todas las partes de tu mensaje a HTML (con la función htmlentities()), de modo que cuando le llegue al destinatario, sepa que es HTML y entienda los códigos de acentos y caracteres especiales, por ejemplo "á" en vez de "á", etc, sin necesidad de codificaciones extras...
Código PHP:
// Por ejemplo:
$texto.="Nombre:". htmlentities($HTTP_POST_VARS["nombre"]) ."\n";
// Y al enviar el mail:
$cabeceras = "Content-type: text/html; charset=iso-8859-1";
mail($destinatario, $asunto, $texto, $cabeceras);