"Don't browse, search" is already well known demand and it changes the way people expect to use your app.
Recently I needed to finalize first incarnation of my Global Search feature in Kexi. Being late by two days after Calligra beta 3 tagging, I made it fully working only for RC1 now. But it's here.
What I needed is line edit with completion. You'd say KDE has KCompletion. Well, it could be improved e.g. in areas like model/view support.