Permalinks and 404 Errors, only sometimes?!

I am going crazy trying to figure out what’s wrong. I have deactivated all and then reactivated plugins one by one, trying to find the issue. I removed one plugin thinking it was the problem but it’s not. What is happening is when I click the main nav buttons in the main menu for the site and just browse around going up and down the menu clicking buttons, sometimes the pages load and other times I get a 404. There’s no rhyme or reason to it, and it almost seems that if I wait longer between clicks (I mean like 30 seconds) the pages tend to load without 404 error. What could this be? Do I need a caching plugin maybe?