Si usas un "alert()" de javascript .. tendrías que redirecionar en javacript también:
window.location="nosedonde.tal";
(o algo así .. confirmalo en el foro de javascript).
Pero .. técnicamente NO es correcto que tengas ese script de PHP que hace un proceso de insercción de datos en tus BBDD y ahí mismo muestres mensajes de error o exito .. se trata de que redirecciones a otro script donde será donde presentes tus mensajes de error o existo, para eso es neceario que -quites- todo ese HTML que ya tienes ahí (en la cabecera y demás) y todos los mensajes de error/exito (echo ... y "alert()" de javascript).
Para esto, ayudate de una variable de control para tal fin y así identificar que mensaje debes mostrar:
Código PHP:
header ("Location: mensajes.php?msg=1");
exit;
y en mensajes.php . .compones una página HTML cualquiera y detectas o filtras la variable $_GET['msg']
Código PHP:
echo "Mensaje: ".$_GET['msg']; // aquí ya lo procesas con un array o similar para mostar una "frase" en consecuencia ..
IMPORTANTE: Si optas por la solución que te planteo .. QUITA todo ese HTML que tienes ahí en ese script NO corresponde. TU script no va a mostrar ningún mensaje .. sólo redireccionará e identificará que mensaje se ha de generar.
El problema de usar la técnica que usas en estos momentos es principalmente la de que si recargas la página en el mensaje de "exito" . .veras como se genera un nuevo registro en tus BBDD .. tantos como el usuario "malicioso" se aburra de recargar la página .. eso se evita con la técnica que te menciono.
Un saludo,