The answer lies in how and where menu_tree_page_data is being called.
For the navigation, Drupal will call *menu_tree_page_data* via menu_navigation_links which will only return a single level of links. You can follow this function up to menu_main_menu and then template_preprocess_page before it (which is how it ends up as a variable in page.tpl.php)
However, if you insert a menu as a block *menu_tree_page_data* is called by menu_tree (which calls menu_tree_output immediately after which does some additional work to the array for the final markup.) After both have run you have your whole menu tree available as an array which I then ran through some custom PHP code to loop through the array and render it into an HTML list.
p.s. I also did not use any of Drupal's default menus. I created my own because I needed control of how my mark up was built (and because I had trouble getting control of the 'links' hook to use with theme_menu_link.) I defined my own theme hook ("THE_MENU_NAME") corresponding to my menu name and also my own theme template which is where I did all my markup building before rendering.
theme('links__system_main_menu', array('links' => $main_menu, 'attributes' => array('id' => 'main-menu', 'class' => array('links', 'inline', 'clearfix', 'main-menu')), 'heading' => array('text' => t('Main menu'),'level' => 'h2','class' => array('element-invisible'))));
theme('THE_MENU_NAME', array('menu_tree' => $menu_tree));
I hope this helps some people out there.