Apple - 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.

If your notes are in iCloud, make a local backup. Then in iCloud settings uncheck Notes. Your Notes will all be removed. Now turn Notes back on. They should all return and this force an index rebuild.

Notes are stored in under Library/Containers/com.apple.Notes in your user folder. You can force just the notes to be reindexed by Spotlight using the following command in the Terminal:

mdimport ~/Library/Containers/com.apple.Notes

Tested on macOS 10.11.