My old desktop-based email reader could do it though. I definitely feel like I lost something here. Even just a KEYWORD* search would be an improvement, and that does not require a bigger index.
Most likely it was just doing an unindexed search over the whole thing. This works, but requires a significant amount of resources - both CPU time and IOPS - for people with large amounts of email. It's also slow unless you have only a small amount of email or it's all in memory already. So it's not really feasible for a free, shared service that offers multiple gigabytes of storage space.