Since upgrading to MacOS High Sierra, I can't search for files using just labels anymore.
For instance, I created a folder called "test", containing a folder called "folder", with the red label (called "Red"). If I select the Red dot, then the folder does not appear. But if I search for the term "folder" or if I search for "tag:Red" then it will appear just fine.
I've already tried resetting Spotlight by adding the folder, and even the entire drive, to Spotlight's Privacy tab, then removing it to force it to re-index. I indeed saw the re-indexing seem to take place, since the CPU on the mds processes spiked for about an hour.