Besides than storing null values in the Agent field of the DB I just dropped the FK that wasn't mandatory being the input of the combobox already driven and not letting the user put wrong info and replacing the "null id" with 0 (my Id field is an identity that starts from 1, so there're no problems doing it).
The code to populate my combobox and to bind it during form loading is the following:
Dim cmb_Items As New Dictionary(Of Integer, String)
cmb_Items.Add(0, "")
For Each item As Agent In AgentList.CreateAgentList()
cmb_Items.Add(item.Id, item.AgentCode)
Next
cmbAgent.DataSource = New BindingSource(cmb_Items, Nothing)
cmbAgent.ValueMember = "Key"
cmbAgent.DisplayMember = "Value"
cmbAgent.DataBindings.Add(New Binding("SelectedValue", AgentBindingSource, "Agent", False, DataSourceUpdateMode.OnPropertyChanged))
Not exactly the solution I had in mind in first place, but it works like a charm!