I seem to have a similar or the same problem:
Steps:
1. Create a note in iOS 9.2 e.g. containing the word "flabbergast".
Try a search for this word in the notes app. Note will be found.
2. Edit this note on another device. (In my case an iPad mini running iOS 7.x.)
E.g. Change the word to "flabbergast123".
3. Go back to the first device running iOS 9.2. Wait a minute for the note to update to the edited version from the other device.
Do a search for a word "flabber..." in the notes app.
The note can't be found. No search results.
What an unpleasant bug to say the least.
Seriously Apple?
P.S.
I'm running the "old" notes app (without the drawing features) on both devices.