I have the same problem with Yet Another Related Posts Plugin 3.2.2 (similar in concept). It sort of works, but I get a lot of 404’s — perhaps 20-50% of the time, depending probably on MySQL database load and associated timeouts when calculating the related posts to, well, a post.
I just noticed this by mere chance… I’m maintaining some 30+ sites with WP, and slowly moving them all to W3 Total Cache. Just two of them had this frequent “404” issue; I assumed this was just because my own Internet connection was slow (which would be strange, since the 404 I get is WP’s own, not a browser timeout…) or a particularly heavy-traffic day on a shared server. But then I tracked down the issue to the “related posts” plugin, which was present just on those sites where I got the most 404’s.
On a different site which had its own related posts plugin from a commercial template, the same thing happened! Curious that OutBrain’s plugin also has the same issue. Hmm. I wonder what Edge has against related posts 🙂 But it’s curious, isn’t it?
Are there errors in the error log when these 404s occur?
Oh dang. I should have added an explanation… I found out what was wrong.
Apparently, in some cases, the overall processing time of WordPress with all the plugins I have will go beyond a certain threshold. Since I’m on a shared server at DreamHost, they just automatically kill the processes when that happens — and thus the 404s (no, they don’t show up on the logs as errors, but I can see the processes being killed). This was actually explained to me by DreamHosts’ technical support.
This obviously happens more frequently on my most busy sites, which, in turn, are the ones with the most plugins as well! Specifically, “related posts” plugins are apparently the source of a lot of processing and very easily reach that threshold.
To sidestep the issue, I started using CloudFlare as a free CDN on top of the busiest sites. Now I still get 404s when logged in to my sites (W3 Total Cache will not cache things for you if you’re logged in), but the rest of the world will be mostly served static pages via CloudFlare, and will not experience any problem.
This all was not apparent to me when posting my comment 2 months ago, so I do apologise if I have mislead anyone in thinking that there were any problems with “related posts” plugins or W3TC…