Its because the site map is heavily cached by the runtime. We use cache depndency files to invalidate the cache, so as long as it can write to the /Data folder a cahce dependency file is created for the site map and then it is touched whenever you delete a page (from the web UI). So if it can't write to the file then it can't invalidate/clear the cache. If you delete directly from the db its never going to clear the cache.
So it sounds like file permissions for your installation are not correct if it can't create/modify the cache dependency files. The3 dependency files are located at /Data/Sites/[SiteID]/systemfiles where SiteID is usually 1 for the first site. If you see files there try deleting them and see if they come back or not. They should be automatically re-created if you delete them then touch Web.config. If they are not created then its a permission problem preventing it from clearing the cache.
You can manually clear the cache by touching Web.config file, ie download it and upload it or type a space in it and save it.
Hope it help,
Joe