Pensandoci un attimo, poichè hai milioni di files...tramite uno script puoi creare delle cartelle ordinate secondo l'alfabeto e distribuire i files in base alla loro iniziale, in modo tale che, quando lo script di ricerca deve trovare una stringa, scarti tutti quei files che non iniziano con il primo carattere di questa.
In questo modo ne escludi un pò, sempre se hai la possibilità di farlo.

Per la rigenerazione, non so cosa si possa fare oltre la chiamata a una funzione ricorsiva come hai già detto.
D'altronde, per quanto riguarda la velocità della rigenerazione stessa, conviene ogni volta fare un aggiornamento(controllando per ogni file se è già nell'elenco) o ricostruire l'elenco da capo ciclando tutti i milioni di files?
Penso che la seconda sia più semplice, ma non so se sia la più performante.

Ciao

Alberto