Mostly as note to myself, but adsworth has released an updated version of wp_list_pages for Wordpress. It seems to adress every issue i've been looking into the last few days, for autogenerating a menubar based on a page structure! Nice!
I'm definately going to play with this when I get some time to try and fix my site over the weekend.
Edit January 4th 2005: wp_list_pages() has now been integrated into Wordpress 1.5 Beta-1