Has happened to me too. Actually, the Android gmail app is even worse on searching. I often have to launch a browser and search via the web interface because the app returns no results.
My experience with the Android App is that search seems to be local only. So if the email is older than the retention policy or handled elsewhere then it's unlikely to show up there. Emails deleted on the desktop are notoriously invisible on mobile.
