For people like me, who are addicted to Klipper: Klipper has search as you type. Just click on the icon, and start typing away! Only the parts of your paste history that match the typed text will be shown, the irrelevant entries will be hidden. This allows you to set the history size to a huge value, while Klipper still remains completely usable to handle. This is just so handy, I'm almost sad I didn't know about this before :) Thanks to ThomasZ for pointing this out, or I'd have never known.
This may be another usability thing to consider for KDE4 development: how to make it clear that something has search as you type, and how to start it. Apparently more applications have it, but it is unclear which apps have it, and how to activate it in the different apps. For example, while it's started with just starting to type in Klipper's popup menu, in Konqueror you need to type '/' to start it. I'd bet only a few people actually know about this cool little feature, just because it's completely unadvertised and hidden.
Quite often, these small and incredibly handy features only get to my ears through word of mouth (just like I only knew about drag&drop from ksnapshot to konqueror because I heard it from Boudewijn, and about ~/.kde/env/ because dfaure told me). We most certainly need to promote these small tips and tricks, especially if we can't advertise their availability well in the application (due to clogging the UI, for example). The KDE Tips and Tricks wiki page is a good start, but we might want to promote that page more. Adding more stuff to it, possibly categorized, would also be a nice thing to do.