I wasn't suggesting timing things but your description of 1/10th of a second does give a clearer picture of what is happening.
It does seem odd since I don't get that experience on my much slower machine, even on ST2.
I can sometimes out-type the display of the characters but once I pause the full string and the results flicks up in about 1/10 second after the last key press which is effectively the behaviour I think you are looking for from the 'wait to load results' (although by a less elegant path). It never gets a long way behind me.
Things get much clunkier if I am deleting characters from the search string.
But maybe you are a better typist and a bit more fussy than I am and that is no bad thing.
Expecting the best is how things get made better.
If you have a ST2 licence you might want to give the ST3 beta a try. Speeding up things like GTA is a big part of what ST3 is about and it is noticeably faster in my experience.