Somewhere else it was suggested to create a new Notes folder, and move all the notes from one folder to the new one (and back if you want):
- Create new Folder ("New Folder" on the bottom right of the Folders screen)
- In the default Notes folder, click Edit (top right)
- Select Move All (bottom right)
- move the notes to the new folder
Now you can either wait until the Notes are moved and then work with this new folder (which includes the rebuild of the index), or chose to move them back in the original folder the same way (which also includes a rebuild of the search index).
Please note that the new search does not work instantly. I had several hundred notes, and it took a while until the search finally worked. Initially it seemed as nothing has changed - I could not even search and find the first note that was at the top of the list. But after about 15 minutes, the search worked and was covering the whole app. I guess it works in the background for a while.
Also note that I did fix this in combinations of the other methods suggested - so it's not 100% proven which solution works best, but why not try all?