wp_list_pages by taxonomy?

wp_list_categories()

Would be the way to go for taxonomies. Further functionality can be done either with a custom walker on this function (This seems to be the one resource: http://scribu.net/wordpress/extending-the-category-walker.html)

or write a custom SQL script.

In the end, I went with wp_list_pages and sorted by custom post type where:

post_type => 'custom-post-type'

is listed as an argument.