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.