No tiene nada que ver con
$_SERVER['HTTP_REFERER'], ni con el
header.
Seguramente estas utilizando Internet Explorer, para esto existe un truco:
Enviar por url una variable con un valor aleatorio.
Código PHP:
header("Location: ".$_SERVER['HTTP_REFERER']."?var=".rand());