No puedes tener nada de HTML por delante de un header() .. es decir nada de "salida" al cliente (navegador).
Deberías hacer un header() de redirección en
Código PHP:
if (mail()){
header ("Location: dondesea.php");
exit;
}
El mensaje de error o exito lo presentarás en la página que llegas al redireccionar sea si misma u otra ..
Para eso tendrás que tener alguna variable de control para saber si tienes que presentar el mensaje o no:
Código PHP:
if (mail()){
header ("Location: dondesea.php?mensaje=blabla");
exit;
}
Código PHP:
if (isset($_GET['mensaje'])){
echo "Mensaje: ".$_GET['mensaje'];
}
En $_SERVER['PHP_SELF'] tienes el nombre de tu script en curso (ejecutandose) .. puedes usarlo para el "location"
PD: usa los arrays superglobales $_POST, $_GET .. etc en todo .. no en parte como ahy los mezclas al usar $HTTP_POST_VARS .. y afines.
Un saludo,