I'm with you: I do the same thing(ctrl+k) and rarely if ever use the search bar. But a surprising number of people still do.

The AJAX suggestion is good. One of our requirements though is minimal effort on our part(we've got a real startup as our primary job).