404 response not working

[deepsand]

Have you tried using a server side script other than PHP?

[freezea]

If you are handling the 404 error pages in PHP yourself, you need to send out the correct HTTP response header and then DO not redirect the user with a "Location:" link. Most often, this is the case when these issues arise.