Did you delete them via Explorer? Depending on how many books you've had on your device, you've probably got a ton of index files in the system folder, which is hidden by default. See
this post for details how to get there.
Once in there, you can open the Search Index folder and empty it.