Pero hay que aclarar que para usar header() es necesario NO tener NINGUNA impresión en pantalla (en su código tiene HTML) y siempre es buena compañia un 
exit después de dicha función. 
www.php.net/header 
Quizá le intereze más una opción en JavaScript. Solo coloca esta línea en el <head>: 
 Código HTML:
 <meta http-equiv="Refresh" content="X ; url=pagina.php"> 
  Donde "X" será el tiempo en segundos... y "pagina.php" será la página a redireccionar. Verás que de esta forma entonces podrás colocar un mensaje en el mismo archivo; quizá algo como "
El correo ha sido enviado satisfactoriamente. Será redireccionado en X segundos aproximadamente" 

... algo como lo que usa este foro a el loguearte. 
Igual cabe la aclaración de que es tema común así que esta la invitación a que hagas uso del buscador...  
Saludos! 
