WP Super Cache returns the wrong header for cached 404 pages.
Non-cached:
ash@ash-workstation:~$ curl -I http://blog.ash.ms/404page
HTTP/1.1 404 Not Found
Date: Sat, 03 May 2008 07:43:36 GMT
[...]
Moments later:
ash@ash-workstation:~$ curl -I http://blog.ash.ms/404page
HTTP/1.1 200 OK
Date: Sat, 03 May 2008 07:43:39 GMT
[...]
This is a serious issue, as search engines respond strangely to these pages. Setting the status to "half on" bypasses the super-cache, and fixes the problem.