In theory, there's nothing stopping you from creating a javascript indexer, and update the index whenever the user logs in and reads (thus decrypting) an email. The updated index is compressed, encrypted and sent back to the server.

You could have multiple megabyte sized indexes, for example each covering a certain timespan. The default search action would be to search, say, the preloaded index for the last month, and the user will expect an "All time" search to take a bit more as more indexes are downloaded. (Patent pending)

Yes you can, but only by Subject (at least that's how it seems to me after some tests)

It's webmail. Everything is stored on their servers.

It can't be searched on the server. The article says "The app is encrypted end-to-end and, like Apple's iPhone, can't even be accessed by the company itself."

Everything available OB the app is available in the webinterface (I am a protonmail user)