Bueno, supongo que está claro que si no quieres que te redirija tendrás que borrar el header();
Si además lo único que buscas es que te ponga un mensajito de enviado correctamente coloca este código en lugar del header();
Código PHP:
$enviado_bool = true;
Y dónde quieras que aparezca el mensaje pon:
Código PHP:
<?php
if($enviado_bool == true){
echo '¡Su mensaje ha sido enviado correctamente!';
}
?>
Al hacer el submit del form la página se recarga, si se ha enviado y has escrito lo de $enviado_bool = true; entonces se definirá esa variable y al cargar el resto de la página entrará en ese if().
Si quieres algo más complejo especifica, Suerte!