I may be in the minority, but I have relatively few books on my reader at any one time. I have calibre server setup so that my "true" ip address
http://7x.x5.xx8.79:1xx8/ can be accessed even when I am away from my home network. I can use the browser and find books in so many different ways if I want to add books to my device on the go.
I also don't have thousands upon thousands of books, in any case. I am amazed at how many I have purchased in three years, but it really isn't all that hard to keep things sorted just using calibre. It helps that I used calibre from pretty much day one and I have always added books one at a time as I buy them.
For the books I do have loaded on my device, search really works for me if I don't remember the complete title of a book or the author, or if I have placed it on a shelf whose name I can't remember at the time (don't laugh, it happens).