I have a blog running the latest stable version of WordPress on a dedicated virtual server with the following situation. (Replace [caching plugin] with W3 Total Cache, Hyper Cache, or Quick Cache, as I've tried all three with the same results.)
[caching plugin] is disabled. I visit a known bad link on my site (http://example.com/xyzz/) and receive a 404 error page. I can verify in Chrome's Inspector and/or Firebug that the "404 Not Found" status is being properly served in the HTTP headers.
I turn [caching plugin] on and visit the same URL. On the initial visit I am served a cached page (verified by the debugging comments inserted by the plugin at the bottom of the HTML source) with the proper "404 Not Found" status in the HTTP header.
If I visit the page again (http://example.com/xyzz/), I'm served the same cached page from #2 above displaying the "404 - Page Not Found" error to the user, but with a "200 OK" status in the HTTP header.
If I turn [caching plugin] off and visit the page again, I am again being served an uncached page with the correct "404 Not Found" status in the HTTP header.
Any idea what might be going on here? This is seems to be causing some an issue where Google Bot is attempting to index some non-existent pages because its seeing the "200 OK" HTTP header instead of the proper 404.