Another factor is also the page generation time. In your case I find it rather taken long time to load a page (15 - 30 secs is too long). Have you figured out if you could optimize your SQL tables as well (for example put more indexes on serveral columns for Virtuemart tables)? Is the SQL host ok? What about your backend admin performance?
What is your page size and the number of files being loaded? You can check this with the FF developer toolbar. (information -> document size).
Also note that once a customer had add something into his / her basket the cache is bypassed due to setting a cookie.
Have you enabled and tested also the cache raw mode (this is the fastest mode, 10 or more faster then off)? This because when you are using the raw mode no session is made and no SQL traffic is made unless certain actions are performed (for example when a user adds an item into the basket).
2. About the product that can crawl your site. Personal I've a favour for httrack.org
to crawl websites but on internet you can find many others as well.