Hi all! I know this is a dead thread but I found it while trying to troubleshoot my indexing problems on my 11th gen Paperwhite. Just wanted to throw out there into the void that removing my books and uploading them piecemeal for re-indexing wasn't working, but I found
this reddit thread which did solve my problems. TLDR: plug the kindle into your computer, manually delete all the files from the Search Index folder, which forces a reindex.
Just in case it helps someone else searching Al Gore's internet for answers!