Until recently, I did have over 1000 books on my K3. I just went through last weekend and removed any that I've finished but forgot to remove, and reference books for work that I don't need on there any longer. I also took off some that need to be cleaned up and put back on later. Now I have just over 900. Since then I've acquired about 20 books that need to be put on there. But it's not even close to full - I have just over 2gb free.
I don't really have any problems finding what I'm looking for. I have 63 collections; the majority (about 50) are genre collections, the remainder are more prolific or favorite authors, two series, and a collection for my Kindle games. "High priority" titles are in a "Next Reads" collection, but I still jump around quite a bit if I'm in a particular mood and nothing on that list fits the bill.
I'm one of those weird "but what if I'm aaaaallll the way out on the back porch and want to read a book that's not on it?!?!" people that feels more comfortable having nearly everything on the Kindle. It's not a problem now, but if I ever get to the point where I fill the Kindle and have to carry two ereaders with me to make sure I have everything, I promise I will seek professional help.