Поделюсь своим опытом решения проблем поиска:
_ программка Locate32 - это то, что Вы и описывали вначале. Создается база данных, а уж по ней потом все ищется.
_ windows desktop search - аналогичная прога, панель поиска располагается прямо на панели задач.
И в той и в другой проге поиск происходит по мере ввода названия файла (или его части) - уматно смотрится.
вот ссылка на форум:
http://forum.ru-board.com/topic.cgi?...1&start=120#lt
Удачи!