Bueno... Yo tengo una manera de hacerlo que es algo mala... Es que yo trato de buscar soluciones conforme a lo que yo conozco. Sino me equivoco esto se hace con AJAX, pero yo lo haría así:
1. Creo un nuevo archivo que contenga ese mensaje que quieres mostrar cuando se envíe. Digamos que lo llamas "success.php".
2. Agregarías un header("success.php"); a la parte del código donde antes tenías ese mensaje.
Por ejemplo:
if(isset($error)) {
echo $error;
} else {
if (mail("elx.gerald@gmail.com", "Formulario de Contacto", $mensaje, $cabecera)){
header("success.php");
}
else{
echo "El Mensaje no fue enviado correctamente";
}
Podrías probarla solamente, pero estoy seguro que hay otra forma, que no sé dominar.