Sorry to be dense, but I don't understand what you mean by "Search the Index". On the older firmware, which I still have on my PW2, the "Search Scope" drop-down gives you these choices:
- This Book
- My Items
- All Text
plus others for "Kindle Store", "Dictionary", and "Wikipedia".
On my Voyage, with the new firmware, there's no drop-down. If you do a search from within a book, you're doing the equivalent of a "This Book" search on the old firmware. If you do a search from the home screen, you get a series of panels: "My Items" (which is the same as the old "My Items", and just returns hits on authors and titles), and "Text in Books" (which is the same as the old "All Text", and does a full-text search), plus panes for "Kindle Store", "Dictionary", and "Wikipedia".
As I said, I don't believe anything's been removed: it's just differently arranged.
Apologies if I've misunderstood you.