El header lo que hace es mandar a los headres del browser en este caso el location, por ende no esta mal ponerle un exit, y es recomendable hacerlo si hay código siguiente.
A mi me ha pasado en varias veces, pero nunca le dí importancia.
Te pasa siempre en el mismo lugar?, y si cerras todo (los browsers) te sigue pasando?
Intentaste poniendo un no cache en php al inicio del script?
EJ
Código PHP:
<?php
header("Cache-Control: no-cache, must-revalidate");
header("Expires: Mon, 26 Jul 1997 05:00:00 GMT");
?>
Sino intenta haciendo este location desde js a ver si repite esta anomalía EJ:
Código PHP:
<?php
echo "<script>window.location ='pagina.php';</script>";
exit;
?>