Sorry I didn't reply sooner, and for bumping a now old-ish thread, and thanks again. I have been thinking about your response and testing various things. I now think you are right in that the counts need to be precalculated and stored in a "counts" table, and then just re-calculated when an update occurs to a product involved in the counts.
The bit I'm having trouble getting my head around is how to calculate all of the counts efficiently, even on a nightly cron. Because the number of counts required grows exponentially with both the number of products and the number of count options. I believe there are millions of different counts in my example (Zappos) as they are stackable (i.e. you can select multiple options from each field).
Right now, I am caching on the fly with 3 hour cache after a cache miss. This causes data to be out of date sometimes, but when you get a cache hit its super quick - just not so quick on the cache misses. So I have inconsistent page load times. The DB servers could also be vulnerable to (D)DOS if someone threw rarely-used random parameters at it.
I need to take another step back to think about it. I wish I could find some more info on it... but I'd like to update this thread when I make progress.