Not quite true. You can enable persistent storage in your browser or the app and enable the app/web app to cache all email you can search the message content too. And other folders. I know this because I use Proton and it works great for me, it searches everything.
I don’t use Tuta but this should not be the case either.
K9 mail is another great email app for Android. Give that a try. It’s quite popular and reputable of an app and it was remade a couple of years ago I think.