I have grown to hate NextGen over the last year or more and when I need thumbnails that link to full sized images I've started using
http://www.viper007bond.com/wordpres...ive-galleries/ with the standard WordPress galleries.
You can view an example of it on one of my client's sites here:
http://www.keithbmachineworks.com/tanane-whitfield/
If you peak at the code, I've used the exclude tag to keep one photo out of the gallery and remains full sized. It's being used on a few of my client sites now and they all love it.
Doesn't totally answer your cache issue, but it does eliminate what I consider a slow-loading, bloated plugin. My other question would be - are you prepping images for the web properly to reduce bandwidth?