Если пользователь попадает на страницу A, и эта страница не существует, не перенаправляйте: просто отправьте код ошибки 404 со страницы A - и, если вам удобно, HTML-контент, указывающий, что страница не существует.
Таким образом, браузер (и это еще более верно для сканеров!) будет знать, что страница, которая не найдена, является страницей A, а не чем-то еще, на что вы пытались перенаправить.
То же самое относится и к другим видам ошибок, кстати: если конкретный URL-адрес соответствует ошибке, то код ошибки должен быть отправлен с этого URL-адреса.
В принципе, достаточно простого:
if (page not found) {
header("404 Not Found");
echo "some nice message that says the page doesn't exist";
die;
}
(Ну, конечно, вы могли бы вывести что-нибудь более приятное; но вы поняли ;-))