The reason you can only search for whole words is that it's straightforward to build an inverted index for whole words, but it takes dramatically more storage to make an index to search for arbitrary substrings, since there are exponentially many substrings of each string, most of which you would never want to search for.
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.
