Matrix does all of this. When you log in on a new device, you verify the login on an old device where you are already logged in (or provide the master key, set up when you created your account).

Some clients will indeed cache your entire chat history to provide search. And not all rooms are encrypted, you can disable it for rooms where it's unwarranted.

And as Signal/WhatsApp show, doing all this on device is quite doable. It's just a pain sometimes with the message history not also being stored on an always accessible server, and messaging relying on always going through that one, single, primary device.