I really would have thought it is a typical indexing problem: too many books at once on the Kindle. (it happenen to me with my first Kindle; loaded 1100 books in one go
).
But if you say that, when you do a random search; it shows ' no items indexing' then it must be something else. The only thing, apart from the battery being defective, could be the downloading.
Did you check if there's a book downloading endlessly? Home-menu-view downloading items. That last one should be greyed out, otherwise there's downloading in progress. It this is the case, you could try sending that book once more from your ManageYourKindle page on amazon.com.
Apart from that, I would charge the Kindle fully (let it charge overnight) and restart it: home-menu-settings-menu-restart.
It this doesn't help; phone Amazon and tell them about it. Good luck.
edit: the WIFI shouldn't make that much of a difference, but it could if your Kindle is already unstable.