I tried deleting the DerivedInfo folder as described here, but the problem persists.
The notes which aren’t found with in-app search are also missing from the results when I try to find them in Spotlight (Command+Space).
If I edit a note’s contents, then it will become searchable again. But I don’t think that’s a good long-term solution.