Random (wrong) results when Drupal's "block cache" is enabled

As soon as I enable Drupal's "Block cache" option I get random and wrong results for the term values in the blocks created by nodeterms.

I added 'cache' => BLOCK_NO_CACHE to your code but can't find out why this doesn't work.

case 'list':
  $blocks = array();
  if (count($vocabularies)) {
    foreach ($vocabularies as $vocabulary) {
      $blocks[$vocabulary->vid] = array(
        'info' => 'Vocabulary: ' . $vocabulary->name,
        'cache' => BLOCK_NO_CACHE,
      );
    }
}
return $blocks;

Any help, idea would be appreciated.