Sometimes just after loading a book onto my Kindle, I get a message saying "Your search can not be completed as this item has not yet been indexed. Please try again later." whenever I try to search. Also, I can't seem to delete documents that have not been indexed.

Is there a way to find out which document(s) the Kindle is currently indexing, and perhaps even find out its progress?

Yes. In your Home screen try searching for something (better for something that can't exist like asdgfasdfasd), the Kindle then will show at the end of the search results screen the books that are being indexed.

Excellent, thanks.

Even easier, just type a period in the Home Screen.

Yes. In your Home screen try searching for something (better for something that can't exist like asdgfasdfasd), the Kindle then will show at the end of the search results screen the books that are being indexed.

Yes, it states the numbers of items and on 'enter' , it shows the title of all the books, which can be deleted (5-way to the left), or by going to home--search for the book and delete.
Items that are not indexed will cause problems, so take the time to check this out when you've loaded several books.!