What is the proper function for multi dimensional localized menu?
menu_tree($menu_name) Seems to do that. It runs the items through  _menu_item_localize. 

It works if your menu is translatable. In my setup menu items were not assigned to language, but translated with 18n_menu from site default language.

This atleast gets translated menu. Localized menu might imply also to version where certain items are only shown with specific language active(in that case this answer migth not work).