Not sure what the difference is then. I use iCloud Mail and didn’t have problems with search on iOS or MacOS, I did however have plenty of issues with search when syncing my work Outlook email via Mail.app, so I assumed there was something special about iCloud (similarly to how Mail.app offers push email only for iCloud and FastMail). I’ve imported decades of email into my account so it’s not about a small email volume either.
