The hyperlink control in the controlstrip has a section at the top for 'recently used hyperlinks'.
Any custom URLs you type in the hyperlink control will be displayed there. If you've typed in URLs that point to pages that no longer exist, they'll show up in the list until you've used enough other URLs more recently.
Lower in the list is the 'pages' section.
That section should only contain pages currently in your Muse site.
Are you seeing your deleted pages in the 'recently used' section or in the 'pages' section.
Seeing a screenshot of your Plan view and the opened hyperlink control would be helpful.