Поиск в очень длинном дропдауне

Недавно передо мной встала задача сделать поиск в очень длинных списках с множественным выбором (дропдаунах). Заказчику показалось невозможным найти нужные позиции среди более чем 5 тысяч наименований.
Я искала решение в интернете и нашла несколько вариантов. Все они сильно грузили процессор на больших списках, некоторые не давали возможности выбирать из списка вручную, и обладали еще кучей различных маленьких и не очень недостатков.
Все, кроме одного...

Правде в глаза - вы не можете полагаться на JavaScript

Эта статья – продолжение темы предостережения людей от чрезмерной зависимости от JavaScript.

Возьмем для примера сайт Lala.com (который был в конечном итоге куплен компанией Apple и закрыт). Они загружали весь контент с помощью Ajax. Если вы заходили на страницу сайта с отключенным JavaScript, вы были встречены индикатором "загрузка":