Well, I think it might be same as the problem that was already discussed here several times.
The problem is JS-based menu that has a bug in caching.
Depending on how much a specific category has subcategories (and the whole category tree belllow), JoomSEF is forced to SEO every link to each category again and again. Sometimes it may be dozens of categories, which means dozens of extra SQL queries. (and in case of nested categories quite complicated ones, because if you have set that all categories should be included in the URL, it needs to get from child category all the way to root category).
That can even multiply the number of categories by the ammount of levels in menu. So easily, the number of queries may get even to hundreds!
Normally, this should be suppresed by using cache (both for JoomSEF and the menu module).
But there exists number of menu modules for VirtueMart, where the caching does not work as supposed and all those queries are run with each request.
Therefore, my recommendation is to:
1. either do not use JS menu, that loads too many links at time; (or use AJAX menu, when the sub-categories are loaded on-fly)
2. or make sure that the caching for the menu module works as supposed (than means that the menu is cached as a piece of HTML code and the SQL queries are thus not run with every request)
3. do not use "include all categories" in URL, but use "use only last category"
4. get stronger SQL server :-)
ideally - combination of all
Anyway, the most effective of them all is to reduce the number of SQL queries and functional caching is the only way to achieve that.