It is still busy indexing the books -- hence the wording of the status message.
It can take a while, depending on how many books need to be indexed. You can see how many books still need to be indexed by searching for a nonsense word in the All Books scope.
The Kindle does not distinguish between sideloaded and purchased books. However, purchased books will download extra information that sideloaded books generally don't have, like X-Ray, pagenumber, and Authorinfo data. (Note that there is software to generate guesstimated pagenumbers, or scrape Shelfari/Goodreads and generate X-Ray files.)
Search uses an index created on the device, so it is naturally available to sideloaded books.