Not sure what you mean by "have tried building caches". A cache is built automatically when you visit a folder, that cache should remain indexed unless you add new files or meta tags to it. You are right in that the file has to be indexed for the search to work.

If you try a search with the box checked "include all non-indexed files" it is very slow as it re-indexes everything with each search.

Not sure how this works on a network like yours, but Vista advanced search is fast for meta data if the directories have been included on the index folder list. The initial index process is slow as it took 12 hours to index just 70 gigs on my computer. For some reason the computer occasionally unchecks the drives to index and I have to redo it. Not sure what causes this, perhaps a virus/spam scan for all I know.