I Hope this issue should be in publish instance, as Nav or sitemap iterates and shows only existing pages.
If this issue is in publish, and you have deleted page in author, it will not be deleted from publish, you have to manually delete it from publish.
To follow best practice always deactivate page first (deletes page from publish) and then delete the page.
Let me if know, in case you are trying some other scenario.
Regards
Praveen