Searches in Outlook (exchange server) hang

We are currently using Exchange version 14.3 (Build 123.4).

It seems that every day when I come in users are complaining that search is not working in Outlook (confirmed on my machine). Users are using a variety of Outlook versions, but most are on 2010 or 2013. None of them are using it in cached mode.

I'm not sure what is actually getting it going again, but I've been trying the following:

Restarting the following services: "Microsoft Search (Exchange)", and "Microsoft Exchange Active Directory Topology" (plus all the services that require them). Between the two it seems to cover a fair amount of the exchange services.

The first day searches started working sometime shortly after I did that. All the others, I ended up doing ".\ResetSearchIndex.ps1 -force -all" from the shell. Granted it can take some time after resetting the index for it to build up again and work – if that is even fixing it at all. Perhaps just the time it is taking me to do those tasks is fixing the problem.

It appears that ResetSearchIndex.ps1 is not necessary – but one of the services that restarts with "Microsoft Exchange Active Directory Topology" is (though not either of those restarted with "Microsoft Search (Exchange)").

Running Test-ExchangeSearch -Identity <username> -Verbose yields a MapiExecption "Unable to SetSear" before the message gets cut off the console window and this:

    VERBOSE: [14:36:32.975 GMT] Test-ExchangeSearch : Initializing Active Directory server settings for the remote Windows
    PowerShell session.
    VERBOSE: [14:36:33.162 GMT] Test-ExchangeSearch : Active Directory session settings for 'Test-ExchangeSearch' are: View
     Entire Forest: 'False', Default Scope: 'domain.com', Configuration Domain Controller:
    'gc.domain.com', Preferred Global Catalog: 'gc.domain.com', Preferred Domain
    Controllers: '{ gc.domain.com }'
    VERBOSE: [14:36:33.162 GMT] Test-ExchangeSearch : Runspace context: Executing user:
    domain.com/Users/ExchangeSearchAdmin, Executing user organization: , Current organization: , RBAC-enabled: Enabled.
    VERBOSE: [14:36:33.162 GMT] Test-ExchangeSearch : Beginning processing &
    VERBOSE: [14:36:33.381 GMT] Test-ExchangeSearch : Instantiating handler with index 0 for cmdlet extension agent "Admin
    Audit Log Agent".
    VERBOSE: [14:36:33.537 GMT] Test-ExchangeSearch : Current ScopeSet is: { Recipient Read Scope: {{, }}, Recipient Write
    Scopes: {{, }}, Configuration Read Scope: {{, }}, Configuration Write Scope(s): {{, }, }, Exclusive Recipient Scope(s):
     {}, Exclusive Configuration Scope(s): {} }
    VERBOSE: [14:36:33.599 GMT] Test-ExchangeSearch : Searching objects "user" of type "ADUser" under the root "$null".
    VERBOSE: [14:36:34.192 GMT] Test-ExchangeSearch : Previous operation run on domain controller
    'gc.domain.com'.
    VERBOSE: [14:36:34.207 GMT] Test-ExchangeSearch : Processing object "domain.com/Org Name/Users/User Name".
    VERBOSE: [14:36:34.738 GMT] Test-ExchangeSearch : Searching objects "Mailbox Database" of type "MailboxDatabase" under
    the root "$null".
    VERBOSE: [14:36:34.785 GMT] Test-ExchangeSearch : Previous operation run on domain controller
    'gc.domain.com'.
    VERBOSE: [14:36:34.831 GMT] Test-ExchangeSearch : Admin Audit Log: Entered Handler:Validate.
    VERBOSE: [14:36:34.847 GMT] Test-ExchangeSearch : Admin Audit Log: Entered ClassFactory:InitializeConfig.
    VERBOSE: [14:36:34.925 GMT] Test-ExchangeSearch : Admin Audit Log: Exited ClassFactory:InitializeConfig.
    VERBOSE: Testing Exchange Search.
    VERBOSE: [14:36:35.206 GMT] Test-ExchangeSearch : Resolved current organization: .
    VERBOSE: [14:38:36.061 GMT] Test-ExchangeSearch : Getting catalog state for Mailbox Database "Mailbox Database"...
    VERBOSE: [14:38:36.124 GMT] Test-ExchangeSearch : Catalog state: Notifications.
    VERBOSE: [14:38:36.139 GMT] Test-ExchangeSearch : Getting the indexing state for mailbox "User Name" ...
    VERBOSE: [14:38:36.155 GMT] Test-ExchangeSearch : Mailbox state: Done, Crawl start time: 2015-03-30T13:32:00.
    VERBOSE: [14:38:36.748 GMT] Test-ExchangeSearch : Getting the message indexing state...
    VERBOSE: [14:38:37.653 GMT] Test-ExchangeSearch : Document state: Queued, state = 0.
    VERBOSE: [14:38:37.668 GMT] Test-ExchangeSearch : TimeSinceLastNotificationWasIndexed for MDB Mailbox Database is 337
    seconds.

    Database     Server       Mailbox      ResultFound SearchTime Error
                                                       InSeconds
    --------     ------       -------      ----------- ---------- -----
    Mailbox D... SERVER-NAME  User Name... False       -1         Time out for test thread.
    VERBOSE: [14:38:37.777 GMT] Test-ExchangeSearch : Admin Audit Log: Entered Handler:OnComplete.
    VERBOSE: [14:38:37.840 GMT] Test-ExchangeSearch : Ending processing &