A combo box is really designed to avoid having no selection. As you've seen it is possible to get it in that state by setting SelectedIndex to -1, but that's not really the metaphor the ComboBox designers were going for. The idea is that the user is restricted to the combo box values. So if "Nothing Selected" is a valid value for the box (or at least valid for the initial load) it needs to be part of your data table. It's common to have a row with ValueMember column as DBNull.Value and the DisplayMember as "Nothing Selected" or "Please select a value" or whatever.
Then your UI validation can ensure they didn't leave it on that value.
UPDATE: You can always add the value last minute if you can't add the value from the data source procedure. In fact, some might consider this a good idea since this "nothing selected" option is purely a UI state.
DataRow nullRow = MyDataSet.MyTable.NewRow();
nullRow["VAL_COLUMN"] = DBNull.Value;
nullRow["DISP_COLUMN"] = "Please select a value...";
MyDataSet.MyTable.Rows.Insert(0, nullRow); //might have those parameters backwards..