Except for books with hundreds of TOC entries (and even then in most cases), I vastly prefer the Enhanced Table of Contents. It is not 'eye candy', it enables more efficient navigation in most cases, and lets you browse the TOC without navigating to another location in the ebook. When page numbers are available it also gives you a way to determine how long each chapter/section is. It will also display multiple navlists (e.g. you can have separate navlists for maps or illustrations).
In any case it is similar to what you get on ePub reading systems, and is better than many of these. It is not perfect (they should add an entry on the Go To menu for 'Hyperlinked TOC' when one has been tagged), and the TOC list itself could have some navigation controls instead of just scrolling (which Kindle is not particularly good at), but when this feature showed up, I finally felt I could navigate my ebooks in a more suitable fashion.
It's also straightforward to create a workaround for easier access to the hyperlinked TOC, when that would be useful: create a note at the start of the TOC and use View Notes & Marks (rather than Go To) to navigate there. For extra credit, create multiple notes to navigate to different sections of a lengthy hyperlinked TOC. In most cases this navigation will only involve one additional step (one more touch) than if there were still a link on the Go To menu. These navigational aids will also be available on other Kindle reading systems (with or without 'enhanced' TOC), if the book is downloaded from Amazon (or from personal documents storage).
In my experience, many if not most updates will force re-indexing of all content (as happened for example with the recent 3.4 Kindle Keyboard update). In any case, there is a way to force re-indexing without re-downloading all books: connect to computer via USB, navigate to /System/Search Indexes/, and delete everything in the folder. Eject USB connection, and Kindle will re-create the indexes.