I was talking with another user about changing the Javascript file from a .js.php (dynamically generated Javascript) to a static .js file in the next release. This will certainly be served faster and allow the web server to cache it. The downside is that this static file needs to be writeable by the web server and I'm worried that's going to make the plugin "break" for a lot of people when they're tinkering with their site's files.
I have the current version running on shared hosting and it's still plenty snappy. Try enabling/disabling other plugins to see if one is causing WordPress to take a long time to "bootstrap". Because of how Dave's WordPress Live Search pulls configuration data and search results from WordPress, it basically takes as long as any other page load to do its thing.
Also, make sure you have a PHP accelerator (APC, eAccelerator) installed. They do wonders for WordPress performance.
I might start caching results for anonymous users.