How can I ensure this block is properly cached?
Why not cache it yourself? The Cache API in Drupal 7 is fairly easy to implement and it sounds as if your problem might warrant it. I had this issue with a very expensive function that was used to generate relatively static data and did a quick cache implementation to avoid having to constantly rebuild the query. 

Let's say your existing function is something like this

function myfunction() { 

   $output = (my calculations and logic);
   return $output;

}


A rough way to wrap this in using cache layer would be 

function myfunction($reset = FALSE) { 

  static $output;

  //some unique idenitifier for your specific record, ex. content type+nid
  $cache_key = (your logic here)

  if (!isset($output) || $reset) {

      // check whether or not output has already been cached and if so, use it
      if (!$reset &amp;&amp; ($cache = cache_get($cache_key)) &amp;&amp; !empty($cache-&gt;data)) {

        $output = unserialize($cache-&gt;data);

  } else {

        $output = (my calculations and logic);

        cache_set($cache_key, serialize($output), 'cache', 3600);

        return $output;

    }
}


The cache_set function is the key to this, here's what each of the parameters is doing: 


$cache_key - your unique identifier for you content
$output - the output from your function
'cache' - the specific cache bin you want to use. Most likely, you'll want to use the  default 'cache' bin
3600 - the time in seconds that the item should live before being reset. In this case, this content is set to live for one hour. You can also set it to "CACHE_PERMANENT" to never needing reset or "CACHE_TEMPORARY" to reset the next time the general cache is clear.