When you delete a Page, you move it to the Trash. When a page is in the Trash, it can be recovered by moving it out again. To permanently delete pages the Trash must be emptied.
You can see what is in the Trash (and move pages out of the Trash or delete them permanently) by doing the following steps:
Go to Dashboard > Pages > Site Structure.
Press the Options displayer in the upper-right corner of the Site Structure panel.
Select the Show System Pages checkbox. You should then see the Trash in your Site Structure.
Click on the Trash and choose "Empty Trash". All pages in the Trash will then be permanently deleted.