A tagging/tokenizing input (a.k.a "pill box") web component a la http://harvesthq.github.io/chosen/, http://loopj.com/jquery-tokeninput/, and http://sliptree.github.io/bootstrap-tokenfield/.
Enable use of very large option lists by switching to a search style. After a few characters are input, fire an ajax request to search for matching responses to populate the options list.