While on the phone with Apple Support, I tried just putting a folder in as the instructions say (Rebuild the Spotlight index on your Mac - Apple Support). I was so frustrated at not having any indication of progress as it appears nothing was happening.
In spite of the fact that the Apple Support person told me it could take up to a day or two to complete rebuilding the index, I checked it periodically by searching for "screen" in my screenshots folder with absolutely no results even though most files in that folder have names starting with Screenshot. I even waited overnight to no avail.
I stumbled on your answer and gave it a try with a little fear and trepidation given that I thought maybe the indexing I thought I had already initiated was still under way.
Based on your answer, I tried it again, this time putting the entire Macintosh HD into the Privacy List, clicking Done, waiting 30 seconds, closing the System Settings window, reopening it, then removing the Macintosh HD from the Privacy List, clicking Done, and closing the System Settings window again.
I opened Activity Monitor to see if I could track progress that way. I saw nothing that seemed related. I then decided to do another test search feeling pretty confident it didn't work, surely it couldn't have done it so fast when it did nothing discernible overnight.
But I was THRILLED to see that it fixed my problem already...so fast! (Not sure if the entire index was rebuilt that fast, so might take a little longer to complete the whole process)
I'm wondering if the "official" instructions for rebuilding the Spotlight index should be modified to do the entire hard drive as Christoph recommends.
At any rate, thank you, Thank You, THANK YOU Christoph!!!!