Lo que buscas es similar a los launchers como
http://www.launchy.net/ (que a proposito, hace lo que quieres ya).
Lo que se hace es crear una base de datos donde se almacenan metadatos de los archivos y sobre la que se hace las busquedas. Una forma trivial de hacerlo es usando sqlite + Full text search. Busca en google como se usa el FTS de sqlite.