Any idea what may be causing this? A restart of the Exchange Search and Exchange Search Host Controller services seems to resolve the issue for a short while, before search functions within both Outlook 2013 and OWA seem to fail again for all users.

Hi,

According to your description, I understand that search function failed in both Outlook 2013 and OWA seem to all users.
If I misunderstand your concern, please do not hesitate to let me know.

Is there any relevant error in event log?

Please run Test-ExchangeSearch Identity to test Exchange Search functionality for a Mailbox server, a mailbox database, or a specific mailbox.
More details about Diagnose Exchange Search issues, for your reference: https://technet.microsoft.com/en-us/library/bb123701(v=exchg.150).aspx

Final, please reseed the search catalog for testing:
https://technet.microsoft.com/en-us/library/ee633475(v=exchg.150).aspx

Thanks

RESOLVED - An increase in disk space for the mailbox store appears to have resolved this issue.

• Marked as answer by MR JH 16 hours 40 minutes ago