There could be two contributing factors, both of which are personal preferences found under Setup > Personal Setup.
- Basic Search Type: If your preference is "Contains" instead of "StartsWith", then searches are much slower. Adobe recommends changing to "StartsWith;" but realize that the search term should occur at the beginning of the filename.
- Including UDFs in Search: If this option is turned on, then the system also searches over all custom metadata (User Defined Fields), which slows the search. Turn off this option to speed search (unless you want to always search by metadata as well). These settings are personal preferences, so all users can change these preferences if they want them to persist. There is no way for a single person to change the personal preferences of their users.
You can fin additional information about these options can be found in the Help:
http://help.adobe.com/en_US/scene7/using/WSCAAE9C8A-F172-43a8-B134-6163E7C80218.html