WooCommerce is slow with many categories

I’m struggling a bit with WooCommerce (and WordPress) being a bit slow.
I have a development store for a customer with the following stats

5,319 Products
2,437 Product Categories

Categories are hierarchical like this
/product-category/by-model/accord-ch1-1998-2003/body/accessories/
The default /shop/ page (showing just sub-categories) takes 14 seconds to load.

Stepping through the categories, each one takes less time to load.
/product-category/by-model/ takes 6 seconds to load.
/product-category/by-model/accord-ch1-1998-2003/ takes 1.5 seconds to load.
/product-category/by-model/accord-ch1-1998-2003/body/ takes 1.5 seconds to load.

None of those categories contain products, only sub-categories.

And finally /product-category/by-model/accord-ch1-1998-2003/body/accessories/ the first category with any products in takes a more respectable 600 ms to load.

Taking to load == time to first byte – once the server sends the data, we have DOM ready milliseconds later. The theme payload is about 500Kb per page.

I was sure the issue was with the insane amount of SQL queries it does in the higher level categories.
Before posting this, I moved the site from it’s original home on a low-load, shared Dell R410 server to a VPS on similar hardware so I can mess with apache or MySQL a bit more.
Server performance is good. Load is low.

I’ve tried using an advanced-cache and an object-cache (both memcache based) and I don’t see much gain. When I watch the general MySQL log I see these massive queries go past. None of them are slow according to the slow query log, I can only assume it is the sheer number of them, or the joins it does on the taxo tables. SQL caching is also enabled but doesn’t seem to help much either.

(All other pages load fast, just these Woo categories cause issues).

Using SQL Profiler, I don’t think it is SQL that is slow, more PHP sits at ~100% CPU load whilst WooCommerce does something.

Total query time: 0.09768s for 89 queries.
Page generated in 15.40064s (99.37% PHP, 0.63% MySQL)

Has anyone experienced this kind of behaviour before? I’m running out of ideas rapidly!

Edit

I’m sure it is related to Woo looping over unnecessary terms
The shop home page (/shop/) does a query like this http://pastebin.com/jsiaYenq TWICE!
Which returns ~13,000 rows.

Another similar query http://pastebin.com/B9xhFLFe returns almost the same number of rows.

SQL returns these queries quick, however NewRelic proves that WooCommerce is trying to do something with these massive data sets, that consume 100% of the CPU and take ~25 seconds to complete.

New Relic shows the app sits at the “woocommerce” stage for a long time.

I’m convinced this is the problem!