This is one of the reasons why so many application developers are going crazy with "file indexing" schemes so their own search processes don't become a bottleneck. You might be able to do similar optimization for folders you know don't change that often. For example, use a FileSystemWatcher or similar running in the background to cache information for a large number of low-activity folders and run-time scans for a smaller number of more active locations.
