Instead of using a multiselect box that is pre-populated use jQueryUI Autocomplete to filter the list server side and only return matches to the client (similar to the way the tag selection works on StackOverflow).
There is a good example of selecting multiple values here http://jqueryui.com/autocomplete/#multiple-remote
You can then save the results of the selections in the same way you would process a multiselect.
To implement a hybrid approach where the first letter fetches terms from the server and then afterwards filters from those results, you could use the following (please note that this is completely untested):
Add a global var to hold your results
var results_cache = [];
Use a hybrid source in your autocomplete
source: function( request, response ) {
// get the first letter of your search term
var letter = request.term.substring(0,1);
// check to see if we already have results for this letter
if (!results_cache[letter]){
// no results, fetch via AJAX
$.getJSON( "search.php", { term: request.term },
function(data){
// cache results
results_cache[letter] = data;
// filter results (in case we have more than just 1 character in the term)
response($.ui.autocomplete.filter(data, request.term));
}
);
} else {
// we already have data for this letter, just filter the results from the cache
response($.ui.autocomplete.filter(results_cache[letter], request.term));
}
},
search: function() {
// make sure we have at least 1 character for the term
if (!this.value) return;
var term = this.value;
},