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.