Problem gelöst...
Folgende Möglichkeiten...
1. Anstelle v. ReplaceChild (InsertBefore+RemoveNode) nutzen
2. Span-Element um das Select-Objekt und mit innerHTML das komplette Select austauschen.
Mit beiden Varianten funktioniert das Löschen und neu Aufbauen des Select-Objekt mit mehreren Tausend Options in unter 30 Sek.
Wenn jemand ein ähnliches Problem hat, einfach per mail melden.