Microsoft Exchange Server Search Index Rebuild
When an entire office can no longer search their emails due to lack of network connection (so the error message says), the Database Index may be corrupt.
> Get-MailboxDatabaseCopyStatus * | sort name | Select name,status,contentindexstateLast updated