As soon as you open the History toolbar (Ctrl+H) and start typing, search results will appear instantly. But you have to double-press Tab key to focus the results list and select the right one.
Suggested behavior: Just press down key to go to the results list. See screenshot