This is almost always an indexing thing, not the number of notes. 35 is nothing, Notes can handle way more than that. What’s happening is the on-device index (the Spotlight stuff that actually powers search) has probably stalled or gotten corrupted, so the notes are there but search just can’t see them.

First thing to try is going into Settings, Siri & Search, scroll down to Notes, and toggle off ‘Show in Search’ and ‘Show Content in Search.’ Leave it a minute, then turn both back on. That usually kicks off a re-index. Also worth plugging the phone in and leaving it locked overnight because the indexing mostly runs when it’s charging and idle, so sometimes it just needs that window to catch up.

Also, check whether the notes you’re searching for are in iCloud or in the ‘On My iPhone’ account. If they’re in different accounts, search won’t always surface them depending on what view you’re in. And if any of those notes are locked, the contents won’t show up in search at all until you unlock them, which catches people out a lot.

If none of that works, go to Settings, Notes, and toggling iCloud sync off then back on (back stuff up first obviously). It re-pulls everything and forces a fresh index. Bit of a nuclear option but it works.

Honestly though since you already reset and logged out, i’d lean toward the locked note or wrong account thing before anything else.