I’ve been using Protonmail for years, with many tens of thousands of emails, and this does not match my experience at all. It is far, far easier for me to find old emails sent to my Protonmail account than to my old Gmail account, which seems to randomly decide that some emails shouldn’t be searchable.

With a paid account it is trivial to export your emails as well: https://protonmail.com/support/knowledge-base/export-import-...