Hola,
A mí me parece que el asunto puede estar en la codificación del correo en cuestión. Por ejemplo, yo utilizo la siguiente función para enviar correo:
Código PHP:
function Enviar($correoDestino,$correoRemite,$asunto,$cuerpo,$cabeceras='')
{
if(trim($cabeceras) == '')
{
$cabeceras = "MIME-Version: 1.0\n".
"From: $correoRemite\n".
"Content-Type: text/plain; charset=\"utf-8\"";
}
return mail($correoDestino, $asunto, $cuerpo, $cabeceras);
}
Funciona bien, pero, si el cliente de correo no "reconoce" ni es capaz de tratar, por tanto, la codificación de caracteres "UTF-8", pues ya está el lío con los acentos, por poner un ejemplo de caracteres "conflictivos".
¿Probaste si ocurre lo mismo recibiendo el correo en otro cliente distinto del que usas? Por poner un ejemplo, prueba a enviar un correo a alguna cuenta en GMail, puesto que ahí se trata como se debe los correos codificados con "UTF-8"... claro, que, no sé si es esta la codificación que usas... o si hay alguna "por defecto"...
Por otro lado, podrías probar a indicar en la cabecera del correo (tal como yo hago en la función de más arriba) otra codificación de caracteres... "ISO-8815", se me ocurre, para ver si de ese modo el asunto va como esperas.