Drupal 7 menus in a localized site

i18n / Internationalization module

We use the i18n menu module that comes with the Internationalization module.
While the module provides configuration options for language specific menu items, simply enabling the module creates a new translation text group called "Menu" that exposes all menu items to the translation interface.

You can use the translate interface to translate all the menu items except for once created by nodes for those you should translate the node and specify the translated menu title.

Nodes linked to menu
Nodes linked to a menu will not have their title translatable

Core menus

The module handles all out of the box situations:

Main menu & Secondary menu
The module implements hook_preprocess_page() to localize the two standard menu variables so that $vars['main_menu'] & $vars['secondary_menu'] are localized

Menu blocks
The module implements hook_block_view_alter() to localize all block menus.

Custom and Contrib modules

All other implementations of menus should use the i18n_menu_localize_tree() as those will not be handled automatically by the i18n_menu module function see http://drupal.org/node/1114010.
We use the following to build up a menu in code

<?php
function bb18n_get_localized_menu($menu_name) {
  // Get the menu tree
  $menu_links = menu_tree($menu_name);
  // reform the array to be i18n_menu compatible
  $l_menu_links = array();
  foreach ($menu_links as $key => $value) {
    if (isset($value['#original_link'])) {
       $l_menu_links[$key]['link'] = $value['#original_link'];
    }
  }
  // localize the menu
  if (function_exists('i18n_menu_localize_tree')) {
    $l_menu_links = i18n_menu_localize_tree($l_menu_links);
  }
  return $l_menu_links;
}

?>

Known issues
If you are using the context module with the Menu reaction, any menu reactions you set will get removed by the i18n_module. For details and patchs see i18n conflict - Menu reaction doesn't have any effect I think this is now committed and fixed