Первое, что я бы попробовал, это вызвать InitStorage, чтобы предварительно выделить внутреннюю память для строк.
Из MSDN:
// Initialize the storage of the combo box to be 256 strings with
// about 10 characters per string, performance improvement.</p>
<p>int n = pmyComboBox->InitStorage(256, 10);