404 errors when for logged out vistors

We have peculiar problem with 404 errors. We are tracking through google and a plugin for our hosting wpengine. We are able to recreate some of the 404s and they are genuine. We can only recreate the 404 for logged out users.
For example: The item is shown in the search results, but when clicked on, it produces a 404 error. When we try to duplicate it when logged in it comes up. If you sign out it come up as a 404. So far we only know it is fixable my clearing the cache. Anyone have any ideas on what the problem could be?