Permalinks Problem - serving old pages

All of a sudden, I'm having a weird issue with Permalinks. When set to "plain" setting, all pages are showing up correctly. When I enable "post name" setting, some pages are correct, but some of the pages are showing really outdated page (with outdated navigation and all)


I'm attaching the screenshot of what it's supposed to look like.

- If you click on "contact" link from the main navigation from the pricing page, you get to the wrong contact page /contact (wrong)
- Try clicking on the contact link from the home page, you should get /contact-us (correct)

Also if you look at an old page, pricing for example, hover over "about us" link - you see only 2 sublinks. There should be 4 as on the home page.

Other pages that are old are about us, teachers, workshops & events

I disabled the caching plugin and no difference. I also tried disabling all the plugin and change the theme, still no difference.

And then the plot thickens! I see correct pages when I'm logged in as admin.

I have no idea how to fix this Please help!