I'm also having the same issue. Using LiteSpeed as my webserver, with Disk: Enhanced and Disk giving me random 404 from time to time, that only get fixed when i refresh cache.
Things are getting so bad that the 404 page is in the top 5 pages most see on the blog! Using latest version of WP and W3 Total Cache.
First i thought it was something with my server, but on a test VPS i have with Ubuntu 12.04 + Nginx + APC + Varnish + Percona MySQL, i'm getting the random 404 too...
Any help about it? I love W3 Total Cache and i won't stop using it... but i'm losing trafic because of this error, and it seems W3 Total Cache is the cause :/