How to use the right menu_tree and menu_link depending on region
To theme only specific regions within your drupal page simply filter your css by prefixing your class with the class or id of the region in question. You can find the region by inspecting HTML output. I use chromes inspector which is accessed via inspect element within contextual menu.

#region-sidebar-first .menu_tree menu_link_my_class { css }


and if you want a different style for the right hand sidebar 

#region-sidebar-second .menu_tree menu_link_my_class { css }