The reason search is slow on your computer is just that the app doesn't use the right kind of index, or maybe no index, for whatever reason. I can index hundreds of gigabytes of text on my laptop and have full text search take a couple milliseconds.
The problem is mail servers. They usually don't support search this way, so the client has to download or cache each message to do the search. Gmail gets around this by having their own protocol and the indexes ready.