Одна из ваших проблем заключается в том, что вы продолжаете объединять строки. Это обычно неправильно на всех языках. В JavaScript это будет быстрее:
var a = [];
for(var i=0;i<1000;i++){
a.push(i);
a.push(" hello");
}
var s = a.join('');
Тем не менее, вы должны профилировать свой код и посмотреть, какая самая медленная часть. 800 DOM-элементов звучат не очень, но некоторые браузеры могут зависнуть. Возможно, вам придется с этим жить.
Кстати, с точки зрения удобства использования, 800 слишком много для комбо. Я бы пошел с автозаполнением. В любом случае, здесь вы используете AJAX, так что автозаполнение - еще более быстрый вариант ...