У HTMLSelectElement (http://www.w3.org/TR/DOM-Level-2-HTML/html.html#ID-94282980 ) есть методы add()/remove() для очистки списка опций и добавления опций, а appendChild, если мне не изменяет память? криво работает в разных браузерах.
Еще вариант — тупо заменять селект на новый селект через замену innerHTML на обертке — скорее всего будет работать быстрее.