I'd written a blog post about this Book hierarchy problem back in 2009, and have just updated it with the diagnosis I just went through, and a couple scripts to help with fixing the problem. I tried finding other blog posts about this problem, but couldn't find anything even after trying several search phrases.
The core problem is that entries in the menu_links table were missing. That is - the "book" database table refers over to the "menu_links" database table to record the hierarchy. On the broken site, there was a "book" table entry for each Book node with a "mlid" value, but there was no matching entry in the "menu_links" table.
I had spotty backups for the site - while I have a script making a daily backup of the database and files directory, I don't keep more than a month of these backups. The menu_links entries were erased sometime before October 1, 2015, and sometime after May 15, 2015 (I just happened to have saved a database snapshot on that day). This meant I had a backup database with menu_links entries which were correct six months ago. Fortunately the Book hierarchy on that site doesn't go through much change, and it was largely usable.
The fix was to copy missing database entries from the backup into the live site, and to see what happened. I did the first few of these by hand using phpmyadmin. Each time I had to then edit the node, and save it, and most of the time the book hierarchy would be fixed (for that node) and show up correctly. Sometimes this didn't fix the problem, unfortunately, but I was able to fix those cases by updating the book outline.
I eventually wrote a couple PHP scripts to automagically copy data from the backup site to the live site -- NOTE: I first did this on a test copy of the site, rather than the live site, for obvious reasons. I'm mucking around in the database bypassing the Drupal code, and of course it might have messed something up and I didn't want to mess up the live site. But after I was comfortable with the process, I did go ahead and run this on the live site. Details are in the other blog post (linked above).
While writing this it strikes me that you'll look at this previous paragraph, and think I'm bonkers for not having a deployment/staging site prior to the live site. Thing is that the site in question is a community forum with tons and tons of "user submitted content". That means I don't have a neat tidy situation with a team of content professionals and an orderly propagation of content through layers of staging sites before it's on the live site. Everyone on this site is jointly editing the live site all day long every day, because they're posting comments to each other while discussing electric vehicles.
While this was observed on a Drupal 6 site, the Drupal 7 Book and Menu_Links tables have identical (or nearly so) schema's. That makes the scripts valuable to anyone with a D7 site whose book hierarchy gets similarly mangled.
It is disconcerting that menu_links entries went bye-bye. I don't know what happened largely because I don't have a firm idea of the date it occurred.
I'm posting this a) to help anyone else ending up with a similar problem, b) wondering if this has happened to anyone else ....