Yeah, poor search performance is definitely an application problem here. Lately I've taken to using Cygwin find instead and it runs just as fast as you'd expect. eg

find /cygdrive/c/ -type f -iname '*somefile.tar'