Could work for limited search. For example each term in search index encrypted by the company key. Client passes is also encrypted search term.

Actual content of the messages could be encrypted separately. Client would send separately the selected terms for indexing and the content for each message.