Atendiendo a que mail() de PHP devuelve un boolean (true/false) cuando puede enviar el e-mail (mejor dicho . cuando puede conectar al servidor SMTP que tenga configurado su php.ini .. que no es lo mismo que "llegó" el e-mail a su destinatario):
Código PHP:
if (mail($rec_email, $subject, $msg_body, $header_info)){
header("location: seenviomail.html");
exit;
} else {
header("location: falloenviomail.html");
exit;
}
Con header("location ..") redireecciono automáticamente en función de ese condicional (IF) a una página de "gracias" o de fallò .. para que compongas tu mensaje de error o exito. Ademas te evitas que si "recargas página" (si mostrases el mensaje ahí mismo tipo echo "se envió el mensaje" .. ) provocar envios repetidos de ese mail ..
Un saludo,