I had this problem some time ago last year, and spent hours/days/weeks on the phone with Apple support to prove it. First they didn't believe it. Several weeks and many support people/managers later they admitted that Notes search was flawed.
They promised to fix it but of course didn't give any timelines.
Weeks later, I felt that it improved. But up until today I don't fully trust it and still believe certain strings/substrings won't be found. The issue is, that I can't really reproduce it to start a new case with support. It definitely works better now, but like I said, I have a gut feeling it's still not at a 100% hit rate.
For me this is a source for uncertainty which no notes app should create. Therefore I still think of migrating over to Evernote - but for obvious reasons, Apple does not make it easy to do that. There is no way to bulk export Apple notes, all you can do is export note by note into PDF format, which a) is incredibly cumbersome if you have, like me, more than 1000 notes and b) doesn't transfer attachments properly.
So as per now, I'll continue with Apple Notes and an undefined concern of potentially not finding the note that I'm looking for. Until I have a better idea of what to do.
If I was starting new with a notes app, I would avoid Apple Notes in it's current state, and rather pay for an alternative like eg Evernote. Searching and finding notes at a 100% hit rate is THE core function of any notes app.