pontifex - 6:26 pm on Mar 1, 2011 (gmt 0)
Not sure how you blast out your 404.php, but to really find out what is going wrong, you might want to start at the bottom:
1st: what is the ErrorDocument in your Apache conf file? There should be a general entry like
ErrorDocument 404 /404.php
then (if that fits), we look at the next step - which would be your .htaccess file...
There could be a general RewriteCondition that fits for ALL requests not found. These rules can be tricky. Make 300% sure that none of your rewrites is matching "anything but found"
3rd and last step of bugfixing is the 404.php - which should be a simple check for the header commands there!
If that does not help, fly another round over your access_log AND the error_log and look, what Apache writes there.
Then you should be able to find the bugger!