Re: Search server in default email app
You can't do a search on the phone for what's not on the phone. To search on the server, the server has to have the code to allow the email app to ask it to search. I doubt that anyone has ever written an email server like that.
You can use the email server's web interface - that probably has more options than any email client on your phone. (What you do and how you do it depends on the email server and how it's been set up - some can do searches for all emails still in the account, some can only search the currently showing page, some search headers as well as bodies, etc., etc. You'd have to send an email to the administrator of whatever email service you're using - Google, Yahoo, your ISP, etc. for more information)
If you really need to be able to search through old emails, I'd suggest running Thunderbird on a PC. The search is pretty fast and you can specify folders and/or accounts to search. But you have to let it keep all your emails on the PC. (
Agent (not free) can download headers only, not the whole email, so you can search subject, sender, date, etc., with less storage being used.)