The search in the mail app on iOS is broken. Searched for an email on my phone and it could not find it. Scroll through my email and find it just fine. Use the same search term on the Mac and it found it just fine too.