I would like to add that I experienced a very similar problem on my client’s website. They started getting random 404 errors on two custom post types, events and news. The 404’s would occur randomly on old and new posts multiple times per week. The 404’s would resolve themselves within 1-2 minutes. It was very strange. This went on for months. I tried everything I could think of to solve the problem, resetting permalinks, updating all plugins, disabling caching, etc. I then came across this forum post and tried deactivating the Yoast plugin. The 404’s immediately stopped happening. After several weeks I reactivated Yoast and the 404’s returned. I do not have the expertise or bandwidth to explore the problem further but it was very clear that it was caused by some interaction with the Yoast plugin.
