Search results in Notes on macOS always empty
@MacManager pointed me in the right direction. The problem was that I had excluded ~/Library/Containers from Spotlight. This is where Notes' data is stored.
I did this years ago way before the "modern" Notes existed and had totally forgotten about it. I wanted to stop Alfred from giving me results from that folder.
Apparently, the Notes app uses the Spotlight index for searching inside the app.
Ouch.