> While a mobile client could do the same, it's not really something that you want to do on a battery-powered device

Doesn't this feel like a perfect example of work done at 3AM when plugged in and (importantly) after the battery is fully charged? It won't be perfect, searching for an email in the afternoon that you received in the morning won't be in the index, but I generally don't need search for emails I received so recently anyways

My ActiveSync app does server side search using server side indexes just fine.

I don't know the other servers well but Dovecot has good SEARCH support.