Block cache should set

In normal cache mode menu is the same for everypage viewed by anonymous visitors
Propose to disable cache for block at all

function local_menu_block($op = 'list', $delta = 0, $edit = array()) {

  if ($op == 'list') {
		$blocks[0] = array(
		  'info'       => t('Local Menu'),
		  'cache' => BLOCK_NO_CACHE,
		);

		return $blocks;
	}