Jeff Eaton and I had chatted about book module off and on for the last month when in Dries state of Drupal presentation he mentioned some of the same things as well.  At the code session I hunted several people down and tried to come up with a task based list of steps to get book module to the next level for Drupal 6.

So heres the break down, if no one has any objections I will file them as separate issues.

Separate outline out of book/book content type and make a legacy content type called book for migration purposes.

Allow for multiple root books with their own permissions and /menu blocks

Allow for next/prev automatic links on/off for a given book

    yes this can be done through the theme but a switch would make it more accessible

Versioned pages for each book which affect the tree - support branches/tags to allow for selecting which branch you want to see.

User input multiple relationship (on page or displayed separate block)

Menu system allows you to split menu's into multiple navigation blocks.  Look at integrating book module to register it's menu's with the menu module to create per book modules into the menu system. (per Dries)  This would also bring it more in line with other core modules.

Allow for a given node to be tagged for more than one hierarchy

Use vamcode for the module (per Dries)