The SiteMap data for the menu is cached and there exist cache dependency files on disk that we touch (ie modify the timestamp) to clear the cache.
Whenever new pages are added or pages are deleted the cache file is touched and that should clear the cache. If for some reason (like insufficient file permission) it can't create or touch the dependency file it could prevent the cache from being cleared.
I would look in the /Data/Sites/[SiteID]/systemfiles folder, there should be a file there named sitemapcachedependency.config, it is nothing but an empty text file. It can be safely deleted to clear the cache or just modified. It should re-appear as long as there are sufficient permissions to create it.
Hope it helps,