Page Not Found for anonymous (clear cache fixes it)
Ask your sysadmin about the health and size of cache tables. Being logged in bypasses page cache. Clearing cache truncates them. Last time I've encountered similar effects, they were caused by a bad sector on server's HDD - when cache table grew enough to start using it, caches got all messed up. It was most visible with page cache.