Recycling the app clears the cache. The problem is caused because your file system permissions are not correct, you need to make the /Data and /App_Data folders writable by the web process. We have cache dependency files down beneath the /Data folder, the system needs to be able to modify those files in order to clear the site map cache when new pages are created or when pages are deleted. since it can't modify the files it can't clear the cache.
Hope it helps,