Hi,
Sounds like it is deleting the pages but it fails to clear the sitemap cache. This indicates a file system permission problem because we clear the cache by touching cache dependency files. If you touch Web.config it will clear the cache and the deleted pages should disappear from the site map. However to solve the problem correctly you need to fix the file system permission problem. The /Data folder and all child folders and files needs to be writable by the web process user. If you moved the site from one machine to another some of the dependency files may have funky permissions from the old server. If that is the case then delete all files from /Data/Sites/[SiteID]/systemfiles and they will be recreated as needed.
Hope it helps,
Joe