La consulta parametrizada espera el parámetro que no se proporcionó

Si pasa un valor nulo al parámetro, obtendrá este error incluso después de agregar los parámetros, así que intente verificar el valor y, si es nulo, use DBNull.Value

Esto funcionará

cmd.Parameters.Add("@Department", SqlDbType.VarChar)

If (TextBox2.Text = Nothing) Then
    cmd.Parameters("@Department").Value = DBNull.Value
Else
    cmd.Parameters("@Department").Value = TextBox2.Text
End If

Esto convertirá los valores nulos de la capa de objetos en valores DBNull que sean aceptables para la base de datos.