I figured it out. It's simply that for some reason Recent Notes is hidden/unhidden by the disclosure triangle for Shortcuts. So when I hid the shortcuts to look for the recent notes more easily, they weren't shown at all!
I consider this a bug, no? I can't imagine any reason why Recent Notes should appear only at the end of the Shortcuts list.