No entendiste
en este script
no debe haber NADA de HTML. Ponte a pensar.. ¿Para qué quieres mostrar algo aquí si todos esos mensajes los vas a mostrar en la página siguiente (gracias.php)?
Eso es justamente de lo que estaba hablando antes. Aquí.. sólo PHP, nada más. El html en las otras páginas.
como te dije el header() no va a funcionar si tienes HTML antes.
Intentalo quitando todo el html y poniendo sólo lo que está entre las etiquetas <?php ?>... ten en cuenta de no dejar ni siquiera una línea o espacio en blanco antes del "<?php" porque será interpretado como salida y tampoco funcionará.
Saludos