I had a similar problem about 5 months ago. It turned out to be an issue with the theme I was using for the WordPress-based site I maintain. Apparently, one of the theme functions called "is_user_logged_in()" which ended up getting the "wordpress_logged_in[HASH]" cookie to be dropped. As a result, W3 Total Cache and another plugin I use thought a visitor to the site had been logged in. In my case, I simply commented out the call to "is_user_logged_in()" and I never found out what caused that cookie to be dropped.
I submitted a WordPress bug report and working with a developer, I found the "is_user_logged_in()" function, itself, wasn't doing anything wrong so there's something my theme is doing that was causing the issue.
So, if you're using a custom theme, see if the caching issues persist if you temporarily switch to one of the "stock" WordPress themes.