Thanks to all for the infos!
Right now i am using phpthumbsup and it is working beautifully. The generating of pages after a cleared cache is sped up considerably, due to the on-demand-rendering of the images. And the option not to clear the thumbs cache helps a lot, too.
So i'm fine right now with the original problem.
As for the many images in the navigation:
thanks for the heads up, jgrant and Susan.
The navigation is working fine without the images. As of now the images are injected via JavaScript after page load. It would of course be nicer to have them all in a sprite, but since it is a dynamically generated navigation (duh!), i would first have to figure out how to dynamically build a sprite of all those thumbs and connect all their positions to their place in the navigation structure. All possible, i suppose and probably worth its while. I put it on the to-do list for cleanup in the end
Cheers,
Marc