My chrystal ball says that some queries in Drupal 4.6 indeed were less than optimal. In particular those for the access controll system. Teh chrystal ball recommends to update to Drupal 4.6.
Since you had your chrystall ball I did not have to say... :)
The first slow queries were like:
SELECT DISTINCT(n.nid), n.sticky, n.created FROM node n INNER JOIN node_access na ON (na.nid = 0 OR na.nid = n.nid) WHERE n.promote = 1 AND n.status = 1 AND na.grant_view = 1 AND CONCAT(na.realm, na.gid) IN ('all0') ORDER BY n.sticky DESC, n.created DESC LIMIT 0, 10;
The upgrade was in my to-do list for some time now, so the time has come.
Thanks, álvaro -- http://www.furilo.com