Ты не поверишь… Мой вариант почти так и делает. Он ждет, когда пользователь закончит ввод и только тогда запускает поиск. Плюс, тебе же не критично, что поиск ведется регуляркой? Можно заменить его на indexOf:
http://jsfiddle.net/ainop/g41x6tto/4/
Больше никаких оптимизаций сделать, наверное, нельзя. Я бы перенес все это на сторону сервера и делал запросы через ajax.