After a discussion w/ Jeff Eaton on IRC, here's my attempt at a clear explanation of what this patch actually does now:

    * Removes the hard-coded 'book' type and perform all node actions equally on any node type via hook_nodeapi
    * Achieves 100% integration with the menu system.
    * Stores each book as a menu (i.e. a hierarchy of menu links), and does not maintain a hierarchy at all in the {book} table.
    * All the algorithms have been changed to use the tree data structure returned by the menu system.
    * Breadcrumbs are set automatically
    * The UI is changed, in part, because there is no fixed node type - for example, the 'Outline' tab is always present.
    * The UI is also changed to make it easier to move a node to a distant parent - only the pages in one book are shown at a time, as well as a select to choose a different book. (This also results in a performance improvement, or at least less memory demand.) 

Important note- the new D6 menu system is totally independent of the (now optional) menu module. This can be confusing, since many of the function names were carried over from D5, and they still share the menu_* function name prefix (perhaps this should be changed). In menu.inc is an API for storing an manipulating hierarchies of menu links. Menu module is one interface to that API, and this patch makes the book module another one, but with different assumptions/constraints.

Also, note that the UI changes are a small part of the overall patch, which is fundamentally a movement of this module to use the nodeapi and the new menu system. I realize that it's easy to get hung up on the UI, but please look at the code.