You should rebuilt the index and try to restart the TS (if possible).
Then check how big the .pst/.ost file are. (perhaps one of them is corrupt and has to be repaired).
It is possible that there is a config-problem in the TS.
Hope one of these suggestions will help, if not you should try Lookeen for Outlook searches. This is a search tool for Outlook and at our Company it works pretty good and it is very fast and precise.