sorry but this problem has nothing to do with Spotlight searching cloud server based mail.
this problem is a known issue on iOS and even if the mail is non-IMAP type of account, Spotlight on the iPhone is able to "find" the header info for email that has been deleted.
apple refuses to fix the problem. the problem has been identified since at least 2 years ago.
if you are saying that not just the headers, but the actual bodies of the emails are also able to be recalled after a spotlight search then its probably not a problem of iOS spotlight at all, but rather a feature of how IMAP mail works, and, how you have set the mail parameters.
have you set the mail parameters to delete the mail from the server immediately after being deleted on yr phone, or what?