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.