I have exactly the same workflow, and this is why I just use neomutt on my desktop and the standard mail.app on my phone. Searching via notmuch normally finds anything I'm looking for.