When I looked at the Android-based email apps, they did not usually support server-side searching... but that was quite a while ago! Maybe someone with more up-to-date information can post.
Regarding your so-called trick of de-activating / activating your email account and for a little while getting results in order, let me offer a possible explanation.
In iOS 6, you recall you could configure how many messages to cache locally for each folder in your INBOX... you could set it from a min of 50 to a maximum of 1000. In fact you could use this setting to cache approximately a day's worth of received emails.
Email searches were broken in two distinct stages. Stage 1 consisted of searching over the locally cached emails... and results were instantenous. Next, for stage 2, one was asked about continuing the search on the remote email server... and of course this took some time. Results from this stage were then appended to those results from stage 1. Everything, naturally, ordered by date -- from newest to oldest.
In iOS 7, the configuration of the local cache is gone... they seem to be using a default of 150 or perhaps it is auto-tuned dynamically. Searches still proceed in two stages. In stage 1, the searching apparently takes place over the locally cached emails... and these results *are* returned ordered by date... but quickly thereafter, stage 2 searching at the remote server begins and once those results are collected then local and remote results are aggregated and sorted by category, ie., From:, To:, etc. I think this is what you are observing.
Just now, I am looking at Apple's doc on iOS Spotlight Searching, http://support.apple.com/kb/ht3636. Looking at the section on Mail Searching, one would think that keyword filter could be entered in search box... but I am unable to get consistent results. My understanding is that the previous selective searches (server-side filters) over headers / entire msgs have been turned into gross sub-string searches over the entire body of emails and thus proceed a lot slower. Besides you are flooded with huge number of results, most of them not relevant to what you ate looking. Sort of searching for a needle in a haystack. While previously, one could judiciously narrow down search results.
--d
