The re-indexing indicates, in my opinion, that your Kindle is unstable.
Now I have my new replacement Kindle, I load my books appr.150 in one go, keep it charging for a few hours- check if the indexing is done; and so on.
Try to leave your Kindle overnight for charging and check if the indexing's been done.
It's hard to say sometimes, why a Kindle becomes unstable, but it shouldn't freeze up after highlighting, or spontaneously reboot, or re-index.
Try and phone Amazon; if you're not satisfied with their answer; phone again. The quality of the people at the helpdesk, though always friendly, differs.
Sometimes it's not bad to have to replace the Kindle, as worrying about it also takes a lot of time and energy.
Good luck.