I was getting the same problem after having global cache on and after a while the urls all went haywire. Also in webmaster tools and joomla watch I can see the search bots crawling a whole lot of strange URLs
Which have several sef urls joined together and if you click on them they lead to a broken page.
www.eveadams.com.au/index.php/buy-best-f...ator-start-here.html
Also putting index.php in there.
Now I have a heap of errors in Webmaster tools. Have kept off cache and that has stopped the menu problem but the search crawl errors are still happening.
Any help to fix this would be most welcome.