Navigation nodes != pages. When you delete the page you are not deleting the navigation node that used to point to that page. And vice versa, if you deleted the navigation node (and not the page) you wouldn't have a way to access the page, however the page would still exist (page management). Some people develop the portal where it's a one to one relationship between pages and nodes, however its possible for multiple nodes to point to the same page. There was discussion at some point to delete all navigation nodes that pointed to a deleted page, however, it was considered safer to leave nodes in tact in case they should point somewhere else, and leave it up to admins to delete appropriate nodes.
How would I delete the Navigation node?
I figured it out.