Ну почему, можно индексировать, а можно просто брать и искать по факту запроса, насколько я себе это представляю. Просто работать с индексом - оно быстрее, вроде как. Взять тот же Шиндоуз ХР - если помните, индексацию там можно было отключить, но поиск все равно работал, просто не так шустро...
По теме - ну да, уже прочел, что в KDE теперь за поиск отвечает Baloo, а раньше этим занимался Nepomuk. Копаю в этом направлении, но пока проблему не решил. Хотя на англиском языке уже в паре мест нашел обсуждение похожих проблем.