El header hace lo que quiere y bloque la página junto a sesiones

[Oracles]

Lo de los session_start lo tengo, y todo va perfectamente mientras no tenga que hacer consulta a las BD en las que en algún momento necesite la variable sesión para comprobantes.

¿Cual es el problema de usar headers en los que en la url haya un dato de variable para enviar?

Por ejemplo este es parte del código que no se ejecuta como debe.

Código PHP:

mysql_select_db($bd_base, $con);
        $resultado= mysql_query("SELECT * FROM Usuarios WHERE (User='$AN') ",$con);
        $row = mysql_fetch_assoc($resultado);
        $CANP = $row['Pass'];
        $AC = $row['Correo'];
        
        $ANP = md5($ANP);
        
        mysql_query("Update Usuarios Set Nombre ='$Nom',Apellido ='$A1',Apellido2 ='$A2' Where User='$AN'",$con);
        
        if($NP != '' && $NPR != '')
        {
            if($CANP == $ANP && $NP == $NPR )
            {
                $NP = md5($NP);
                mysql_query("Update Usuarios Set Pass ='$NP' Where User='$AN'",$con);
            }else{
                mysql_close();
                header("Location:Menu.php?Us=$AN&NC=1");
            }
        }
 

Se que entra dentro del elese lo tengo comprobado y que hace el close, pero el header no seactiva, salta al if de la siguiente comprovación que hay abajo, y al final el único header que se activa es el que hay al final de la hoja en el que mando que todo va correcto si no a entrado en los else.

¿Si quiero interrumpir la ejecución del script y que redirija automaticamente en ese punto que comando debo usar como alternativa al header?

He hecho modificaciónes de modo que ya no dice que la página no existe, está arreglado lo de las sesiones, pero sigue saltandose los headers.

Gracias Triby por tu respuesta, tendré todo eso encuenta para mis códigos, son cosas que no sabía ni nunca había leido sobre ello. La verdad es que cookies y sessiones no suelo trabajar con ellas y menos junto a headers, así que todo problema es nuevo para mi y no pillo soluciones optimas sin tener que prescindir de ese tipo de varibales.

¿Debería ponner las comprovaciones antes y al final los headers así como las modificaciones y no hacer comrovación ejecución?