There is a very long history of search complaint threads. After some considerable improvement this year things have gone a bit quiet on that front though. No doubt due to ARC development and release.
We’ve resolved some backend issues with indexing that may have resolved this issue in the cases you’ve reported. There are also minute search improvements included in regular updates that often don’t make the release notes, so I’m curious if the current build (released today), or the previous build, had any positive result here.