Use MYMODULE_theme_registry_alter for overriding theme_menu_item_link(). This is needed only when fragment is saved as a part of the link_path (not in the 'options' array).

Drupal_6_fragments_in_menu_links_module.php

/**
 * Implementation of hook_theme()
 *
 * Inspiration: http://www.lullabot.com/articles/overriding-theme-functions-in-modules
 */
function MYMODULE_theme_registry_alter(&$theme_registry) {
  if (!empty($theme_registry['menu_item_link'])) {
    $theme_registry['menu_item_link']['function'] = 'theme_nodesymlinks_menu_item_link';
  }
}

/**
 * Menu item link theme function with fragment replace.
 * This is needed only when fragment is saved as a part of the link_path.
 *
 * Inspiration: http://drupal.org/node/325533#comment-3460720
 *
 * @see theme_menu_item_link()
 */
function MYMODULE_menu_item_link($link) {
  if (empty($link['localized_options'])) {
    $link['localized_options'] = array();
  }

  return str_replace('%2523', '#', l($link['title'], $link['href'], $link['localized_options']));
}