DescriptionResolved: Moving the active database copies to another node seems to have fixed the search issue. I have rebooted the affected node and tested a single database on the original node with positive results.
The search functionality in Outlook Web App (OWA) is currently unavailable for some users. We have narrowed this down to a specific server and are currently working to resolve. This does not affect Outlook rich clients that are in Exchange cached mode.