I think a possible "solution" would be to put the updating of the history table towards the end of a page request. Currently, the table is updated from node_show. If it were updated (with all neccessery node views) at the end of the page request, it would probably not be faster, but the user experience would be better (or do we only start to deliver the page after _everything_ has been processed?).
So, in node_tag_new() we should only collect the nids in a static array and then later on node_tag_new(NULL, 'update') we could execute the queries (maybe bunching them together in a more effective way, we also do one query per history check in node_last_viewed(), Dries how bad is that query?). This could be invoked in node_footer().
We can easily do the updates in one query, since the history dates are always populated with time() for the complete nids viewed. This would tremendouly help a printer friendly book view, where multiple nids are completely displayed on the same page. Other pages might not gain much from this... Goba