As a followup, tried the same on the C:\ drive on the Windows 7 machine to make sure it wasn't a network issue (eliminating any sort of DFS, non MS server or other possible issue). Same results.

Also tried on Windows 10. Works fine there, so it looks like this search bug was fixed at some point, but not backported to Windows 7.