Non basta un header 404 per redirigere il browser.

Potresti fare così:

codice:
if ($variabile) {
    header("HTTP/1.0 404 Not Found");
    header("Location: /page-not-found.php");
}
P.S. nell'header location usa un URL completo (http://www....)