You can rebuild your search indexes.....
7. Open the System folder on the Kindle disk
8. Open the Search Indexes folder inside the System folder
9. Select all files inside the System Indexes folder and move them to the
Recycle Bin [I.E., delete them]
11. Safely eject the Kindle
12. Disconnect the Kindle from the computer
Restart the Kindle, for good measure.
Then, the search indexs will be rebuild...plug it into power, and wait a few hours or so.