Suche bzw. Indexierung übelst langsam und ohne Strategie

Tach auch, hab mal eine Frage...

wir haben hier auf einem Fileserver sehr viele kleinere Dateien. Die Benutzer müssen immer wieder nach den Dateien suchen. Dabei kommt es eigentlich nur auf den Dateinamen an und weniger auf den Inhalt einer solchen datei.
Die leute haben bemängelt, dass diese Suche in nur einem Ordner bis zu drei Minuten dauern kann. Gut, es sind auch ein paar tausend Dateien, aber trozdem...
Ich bin nun auf die Idee gekommen, den Indexdienst auf unserem W2K-Filer einzuschalten. Der rödelt seid gut 12 Tagen schon an der Indexierung herrum und ist immer noch nicht durch. Seid dem die Indexierung läuft ist es mit der Trägheit kaum noch zu ertragen.
Ich habe dann mal zwischendurch ein Test gemacht, über die normale Suche (Nach Deiten und Ordner Suchen....). Dabei habe ich einfach mal 'Dokument.doc' eingegeben. In der Fensterleiste sieht man ja immer schön wo er gerade durchrödelt. Und er rödelt, und rödelt und rödelt ......... nix gefunen. (Is ja auch O.K. Datei existiert ja net) Wollte auch nur testen ob der immer noch alles abklappert oder ob die Indexierung nun besserung bringt.
Habe dann das Fenster geschossen und ein neues Suchfenster aufgemacht. Genau nach dem gleichen gesucht (Dokument.doc).
Nun stelle sich das mal einer vor .... der durchsucht doch tatsächlich grad nochmal alles und rödelt wieder seine 8 bis 10 Minuten vor sich her.
WAS MACHE ICH FALSCH??????


Ich gebe zu, daheim nutze ich einen Apple mit Mac OS X. Bei dem sieht die Suchfunktion so aus, dass schon während der eingab des Wortes Ergebnisse erscheinen, die sich dann immer weiter reduzieren. Da habe ich die Sachen innerhalb von Bruchteilen einer Sekunde.

Wie bekomme ich das mit Windows hin??
Bin für jeden Tipp dankbar.