Drupal 6 menu system is a big improvement over Drupal 5. Of course, it's new, and like any major rewrite it will take a few iterations to reach its peak.
I struggled recently with the menu system in a website upgrade from Drupal 5. And again rending fiddly table of contents for a site that uses the book module. What I really miss, as with Drupal 5 before it, are some really nice API functions for building, manipulating and rendering menu structures that are defined in the menu_links table.
So, this tutorial explains how to tackle the Drupal 6 menu system to generate the HTML for a subset of a menu. If you are familiar with nice_menus, that module has some helper functions for similar things.