Weird Permalink Behavior - 404 Errors

Greetings,

I'm hoping someone can shed some light on my disappearing blog post permalinks I'm experiencing on one of my sites. I have multiple sites setup with similar configurations but only one of them is experiencing this issue.

My blog posts are disappearing - when you try to access one via the URL, it displays a 404. I know the post is there; I've seen it before. If I go into the Settings | Permalinks page and simply click save again, the blog posts return. My permalink structure is setup to use this format:

/%category%/%postname%/

Clicking save on this page is only temporary, though. Eventually, all of the posts will show 404 errors again.

Has anyone ever seen this before? I started noticing it when I installed WP Super Cache. I've turned caching off but it's still happening.

I am also using Yoast's SEO plugin, using the same settings as on my other 6 or so sites. Is it going to require me disabling plugins one at a time to find the culprit?

Many thanks in advance,

Daniel