Hola
Pues en realidad no estas validando que la entrada ya exista, debería ser algo como esto:
If lb.Items.Contains(tbid.Text.Trim) Then <-- Aqui se valida que solo exista ese id de cliente
MessageBox.Show("Ya se ha agregado.")
Else
lb.Items.Add(tbnombre.Text)
//Aquí agregas los demás datos
End If
Saludos
Antonio Lobo
Mi blog