Thanks again for your help. I installed that fantastic plugin you provided, although unfortunately for some reason it doesn't divulge the SQL of the [DFR:custom views]
Anyway, I took a guess at what the problem was, looked at the existing indexes and have discovered the solution - I think you'll like it:
alter table wp_dfr_shop_p2c add index(cat_id, id);
As it stood, the existing index goes in the other direction - id, cat_id - meaning the entire p2c table has to be scanned when running a p2c.cat_id = xxx type query, which as it turns out is all of our custom views AND many of the queries on our shop (where the queries DO show up thanks to that plugin).
Our shop is now MUCH MUCH faster. Maybe you'd like to test it on your own installations and add this index to the next release? I am seeing pages now respond in sub-second speed where previously some were taking upwards of 20 seconds!
I'm now going to stick the cache on top too but am very happy that Google will now find us to be fast.