Taxonomybased view SQL woes

I work with a newspaper website for three weekly newspapers. Making listings for the different categories as well as newspapers, I have constructed view blocks and pages that sort on domain (with the domain access module) and taxonomy (I use taxonomy_term and just added current domain to the query). However, the queries get very convoluted and slow - especially in listings with a pager. Partly I work around this with the mysql-cache - but as we get new stories every 15 minutes (on a busy day) the cache is blown pretty often. And somtimes kills the server outright (dual P4 - dedicated to this site).

A typical pager query looks like this:
SELECT count( DISTINCT(node.nid)) FROM def_node node LEFT JOIN def_node_access domain_access ON node.nid = domain_access.nid AND domain_access.realm = 'domain_id' LEFT JOIN def_term_node term_node ON node.nid = term_node.nid LEFT JOIN def_term_hierarchy term_hierarchy ON term_node.tid = term_hierarchy.tid LEFT JOIN def_term_hierarchy term_hierarchy2 ON term_hierarchy.parent = term_hierarchy2.tid LEFT JOIN def_term_hierarchy term_hierarchy3 ON term_hierarchy2.parent = term_hierarchy3.tid LEFT JOIN def_term_hierarchy term_hierarchy4 ON term_hierarchy3.parent = term_hierarchy4.tid WHERE (node.status = '1') AND (domain_access.gid IN ('0')) AND (term_node.tid = '22' OR term_hierarchy2.tid = '22' OR term_hierarchy3.tid = '22' OR term_hierarchy4.tid = '22')

Lowering the depth of the hierarchy actually makes things worse (most of the time), apart from the fact that the higher hierarchy pages belong to our most popular ones. Only setting hierarchy to 0 makes i behave reasonably (with a query time of ca 200 ms).

The above query takes approximately 2.5 seconds, and it comes with a companion (without the count) that takes another 2 seconds - as well as the query actually building the view taking another 1.5 seconds. Is there a way to deal with this (apart from not using pagers)?

The only reasonable alternative I've tested was to implement one view per term, which brings the query time down to 80 ms - but that one involves a lot of work, and makes adding new categories a royal pain. Here's what that query looks like:
SELECT count( DISTINCT(node.nid)) FROM def_node node LEFT JOIN def_node_access domain_access ON node.nid = domain_access.nid AND domain_access.realm = 'domain_id' LEFT JOIN def_term_node term_node ON node.nid = term_node.nid LEFT JOIN def_term_hierarchy term_hierarchy ON term_node.tid = term_hierarchy.tid WHERE (node.status = '1') AND (domain_access.gid IN ('0')) AND (node.status = '1') AND (term_node.tid IN ('21','20'))