This means your folder permissions are not correct so it can't modify the cache dependency files to clear the cache. You need to make sure the /Data folder and all child folders and files are writable by the web process, typically NETWORK SERVICE user in IIS 7.
Whenever pages are added or deleted it tries to touch a file that will clear the cache but if it does not have permissions then the cache does not get cleared. Recycling the app pool is just another way to force clearing of the cache.
Hope it helps,
Joe