Depends, on an older phone, downloading all emails just to allow for searches locally won't be very efficient. Log out also becomes a problem, if emails are stored on one device that gets stolen, adversary now has access to the local index since all the keys or on the device usually with no FDE. Meanwhile with gmail a log-out would clear all traces instantly.
Also, not really true of Gmail. Try turning your WiFi off, then deleting your Gmail account. You might have mail stored offline on your phone (let alone any other device), as well as any IMAP or other clients. It's the same or worse.
This step is what I was expecting you to talk about, and it has some tricky subtleties to get right, which is why I looked for it in the whitepaper.
A trivial problem with a naive implementation is being able to perform presence proofs using side channel information: send someone mail containing a terms you want to verify, and watch for the associated high level costs affecting operations that are likely to be incremental index change uploads.
