Best method of caching complex data generated from nodes?

Not sure if the title is good enough to describe this problem, but here goes...

I've had some small input into the KML module (http://drupal.org/project/kml). This generates KML (Google Earth) files which show placemarks for content with locations. While rather cool this can be very slow when you have many nodes with location information.

When I got here, there was no caching in the module and it was killing my site (which is Drupal 5). Most of the slowdown seemed to be from having to node_load all the content to include in the file. What I did was change the code so it makes a list of these nodes, MD5 them, add a little prefix and use that as a cache ID. When a request comes in a list of nodes that are to be included is made, the cache ID made from this, and where the KML data has previously been generated it could be retrieved from cache (node dates are checked as list is being made).

All good, but this relies on that generation of the list of valid nodes. Such a list should including access restrictions.

In D5 I dummied up the node object to pass to node_access easily enough (from a few fields in the node table), but in D6 this doesn't seem to work. Meaning one has to node_load the node the real object, which slows the caching down again.

I'd be interested in people's take on this problem and if they see a better way forward.

For our site I can imagine that a cache based on the request path and roles of the current user will be good enough. Sadly, that is not going to be good enough for everyone so I cannot suggest releasing something based on this.

What is required is a speedy way of finding out if the current user has access to a node (without having to node_load it) or some other more generic mechanism for caching this kind of data that would include all roles/groups/[other access mechanisms].

Help/discussion much appreciated.

Cheers! :)