Improving the search is not an easy topic since Link Library stores the additional link information in a custom table. Search Everything would probably be able to improve basic link search, but it's results would not be shown in a way that would match the rest of your links.
The best avenue is probably to improve the search algorithm inside of Link Library to support quotes, multiple search terms and search operators (and, or, etc...)
The code for the search is actually fairly isolated in the plugin, so someone with good knowledge of string parsing and SQL could enhance it quickly.
I am personally tied up on a long-term project that is going to be keeping me busy until the May-June 2012 time frame, but I could help someone with the right skills to find their way around the code and integrate their work into the plugin.