I don't have any side loaded books but I just tried it in Boardwalk Empire and the search works. I wonder if a restart would help? Sounds like the indexing might have got corrupted.