The problem is most likely a change in file system permissions, the cache is cleared by touching cache dependency files under /Data/systemfiles and /Data/Sites/[SiteID]/systemfiles.
If it can't modify those files then it can't clear the cache. I would try deleting all files from those folders, they should re-appear on their own if file permissiosn are correct but otherwise you will need to fix the permissions on those folders to make sure they arew writable by the user that is the identity on the application pool.
Whenever a page is created or delted it should creatoe or touch a dependency file for the site map so that the sitemap cahce can be cleared.
Hope that helps,
Joe