deleted page still shows up in menu new pages don't

HI you guys Im a photographer and decided to build my own word press website. I installed the Sydney wordpress theme because of the full page display of the home page sliders. The only thing I was really wanted to add to my site was a photo gallery. I decide to delete a page that I titled gallery I also cleared my browsers history but the deleted galley page was still in the menu list. I then added new pages but they didn’t show up in the sites menu list. When I clicked on the deleted gallery the page it said “opps that page cant be found” on this page I then clicked on the search button and then I found all my new pages that I tried to add to the menu list like blog, about and new/gallery only in the search results. They all had my published content in them. Do I need a gallery plug in or a menu list plug in to get my new pages to be on the menu list and not the search result.