We had a user delete an email. I know; we're proud of them too! ;)
Seriously, how long does it take? That was the question. We deleted one over an hour ago, and it is not in the search. It had the exact single word (chamber) in the message body, subject, and from so it was perfectly staged on our side. I have gone into the deleted items, and I see the email we deleted as part of our test.
We'll keep trying every hour until it shows or doesn't, but curious how long it really should take so we can give an honest answer to the user.
I do know all indexing we've never changed in years, so it's whatever is the defaults for SmarterMail.