Can't figure this one out, and running the Windows search troubleshooter found no issues.

Network share \\server\share\archive has a folder hierarchy like so:

2014
2015
2016

Inside each folder is more folders, say 0001, 0002, 0003, 0004 etc.

Inside those folders are files, and here's two examples:
0001_2016-02-12 XXX 01 Thing.pdf
0009_2015-12-31 XXX 02 2016 Something.pdf

If I open Windows Explorer, go to the path \\server\share\archive, and search for "2016-02-12" in the search box in the upper right, guess which file shows up.

If you answered "0001_2016-02-12 XXX 01 Thing.pdf", you guessed incorrectly. Instead only "0009_2015-12-31 XXX 02 2016 Something.pdf" shows up.

Now if I search for "_2016-02-12", both the above named files show in the search results.

So, umm, how do I get search to work properly here?