Windows Search does not find files by name

Question

I'm facing some really sublime issue with windows search index right now and really hope that someone here has a hint on how to troubleshoot, since I can not find any approaches on how to fix windows search besides rebuilding the index, which I've done several times now.

The occuring misbehaviour:

• browsing any share, no matter if it has hundreds of subfolders or just ten plain files in them, windows search does not find files by name.
  • Example: I'm in a share that only has a few files in it. I copy a files name and paste it into explorers search pane - and I do not get any search results
• the contents of any files, e.g. OCR'd PDF or TXT, get indexed properly - and get returned by windows search.

Affected setup:

• Fileserver on Windows Server 2012R2 running on a ESXi 5.5 Cluster
• ~5TB net storage available on ~30 shares, ~3M files total
• Every share is affected - from every client. I do only have Windows 7 machines running in this environment, but a test from a W8.1 machine gave me the same results.

Things I've tried

• completely deleted and rebuild the index several times
• excluded all hidden shares, e.g. my deployment share, from the index
• played a bit with Windows Search Syntax - e.g. searching for filename:myfile.txt or name:myfile.txt
• changed indexing behaviour for test purposes for pdf files: Index properties only instead of Index Properties and File Contents

I'd really appreciate any tips on how to progress - this problem is becoming a real pain for our staff.

Thanks!