- some goals are contradictory (ex: end-to-end encryption and searchable histories)

I still don't buy that. If you do search client-side, then history should be trivially searchable even under E2E encryption.