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)

URL: yogafactoryfitness.com

Example1: http://yogafactoryfitness.com/pricing/
I'm attaching the screenshot of what it's supposed to look like.

Example2:
- 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!