header("HTTP/1.0 404 Not Found",true,404);
а вот так не пробовал?
У меня такая конструкция работает на ура...
А, черт. Логи апачи?.. Так помоему не получится средиректить на 404, и чтобы в лог прописалось 404.. апача ведь выполняет твой скрипт?.. значит, это уже не 404.. а то, что выдается в браузер - получается совершенно другая история.