Not sure how search works at the moment but when I am searching on the server it takes forever. I'm guessing that the search function is not only searching the message headers but also the message body. I'm probably a little unusual in that I have 60,000+ messages in my inbox. However I am a recent iPhone convert and on the iPhone I was able to search my messages on the server in a fraction of the time it takes to search with an aqua mail. I'm not sure how long it would actually take to search through all of my messages because I haven't let it run that long it was taking a long time.
Perhaps a more configurable search functionality ie searching by sent name or received name or subject might make search function more efficiently.
Sent from my Nexus 5 using Tapatalk