Yes, that would be fine and is fully realizable. In the client-server model of end-to-end encryption, a server self-hosted by the user is isomorphic with a user

Yes, that would be fine and is fully realizable. In the client-server model of end-to-end encryption, a server self-hosted by the user is isomorphic with a user's client. They're effectively the same thing. The tricky part here is defining who the user is. If you're implementing end-to-end encryption for data on a per-employee basis, you're back to square one with a self-hosted server. But if you're implementing end-to-end encryption for data on a per-organization basis, and the organization has a self-hosted instance it controls, then yes, end-to-end encryption is compatible with organization-wide message search.