Notes app search is not finding some notes
Much quicker way of fixing this is just to make a new iCloud notes folder, move all your notes into that and back again. This seems to rebuild the index- you can then get rid of the new folder. 
This is useful if like me you don't have a quick option to back up your notes separately.