Block caching when access-restricted modules are enabled We have a module that creates a custom navigation block. It runs a metric ton of queries, and it's really affecting performance. (Note that I inherited this site; I did not write this code!)

We want to cache the block, but the built-in block caching (admin/settings/performance) is greyed-out, with a message below that says block caching is inactive when modules defining content access restrictions are enabled. We do have several modules that have access restrictions, and cannot disable those.

Is there any other way to cache the navigation block? I know about the BLOCK_CACHE_* constants, but am assuming that the built-in block caching needs to be turned on, and that those constants modify the default behavior. If we can't turn on the built-in caching, what (if anything) can we do?
Assuming that the module that creates the block and is this performance heavy is a custom module, a simple solution would be to cache the output of the block from within the block. Take a look at the cache_set and cache_get functions on http://api.drupal.org