What's the name of the folder you're searching for and where is it located on the drive? Which search field are you using.... Mail, Spotlight, Finder, etc.?
I'm using Spotlight and the folder is in Mail. Assume the folder name is "A Big Mystery" and I conduct a search just using "Big".
Spotlight only finds a Font folder containing "Big" even after all the re-indexing, et cetera.
EasyFind locates a couple of folders, neither of which is the one I want.
I tried Find Any File and it can locate six folders with "Big" in the name, including the one I want.
Adding to the mystery is that Spotlight no longer seems to be able to look for text inside a document. The Spotlight test I ran, with a three word phrase that's inside at least 100 Word documents, only generated three results.
After a re-indexing it still only found three...except that they were a different three.