From a command prompt (you shouldn't need admin rights), run "REG ADD HKCU\Software\Policies\Microsoft\Windows\Explorer /v DisableSearchBoxSuggestions /t REG_DWORD /d 1 /f", which disables the web search suggestions in the registry. After restarting Windows Explorer (or logging off and back on), you should have search work how you'd expect.