Bueno, inventando y escribiendo
Creo que es posible colocar un input text al lado y a este asignarle un evento, este llamará una función que modificará los options del select, haciendo una búsqueda por lo que hayas escrito en el input.
Como lo ves?
Los options los generas dinamicamente o estaticamente??