Bueno, en efecto con el mensaje CB_ADDSTRING agregas una cadena al control. El mensaje CB_SETITEMDATA no sirve para eso, sino para asignarle algun "dato" a un elemento que ya este dentro del combobox.
¿Podrías pegar como es que estas mandando llamar a ese mensaje?.
También intenta con el mensaje CB_INSERTSTRING.
Marcadores