performant way to load many complete node-objects
node_load() is the preferable way to load a node object, especially if the node object is passed to some functions.
Take in mind that, in Drupal 6 the result of node_load() is locally cached in a static variable by default; if you are going to load a bunch of nodes, it is better if you call the function as node_load($id, NULL, TRUE). If you are sure that, for some reasons, the code could load the same node in consecutive calls to node_load(), then you can consider resetting the static value after X calls to node_load().
The result of node_load() is not cached, if the $revision parameter passed to the function is not NULL.  

Caching the value obtained from node_load() is possible, and your code could use its own cache for that purpose. The cache should be invalidated when nodes are updated, which includes also the case when a node is reverted to a previous revision.
Rather than implementing a cache in your own module, it would be better to use a module that caches the nodes for third-party modules.

In Drupal 7, both node_load() and node_load_multiple() accept a $reset parameter that resets the node cache kept as instance variable from the object of class NodeController that is created from Drupal, which uses the instance variable implemented by DrupalDefaultEntityController, the class that implements the default methods necessary for an entity controller.