E2EE works fine in browsers, but you run into the same challenges and worse when it comes to usability features like search. On desktop there's (imperfect) indexing of encrypted messages so that you can search encrypted rooms, but I don't think Android has that.
The server-side search feature, which most Android apps use, can't search through your encrypted messages for obvious reasons. Element for Desktop and its forks maintain a local search cache, but this is quite CPU intensive to generate, especially if you're signing into an existing account. I can see why they haven't implemented this on mobile phones, you'd need to leave your phone hooked up to a charger overnight to generate such a cache without draining your battery.
I think this is the result of Element doing exactly what you suggest: support E2EE above all else, "all else" including "being able to search through chats".
You may want to consider XMPP as an alternative to Matrix. I have no idea if and how E2EE search works on popular XMPP apps, but it's worth a try.