C# と VB.NET の質問掲示板

SQLServer2005 + VB.NET2005 で開発しております。
約三百万件のレコードがあるマスタテーブルに対して、
(1)
    Dim strSql As String = "update TMX_ITEM"
    strSql = strSql & " set DEL_FLG = 1"
    strSql = strSql & " where SHOHIN_NO = '" & "12345" & "'"
    strSql = strSql & " and COLOR_CD = '" & "01" & "'"
    strSql = strSql & " and SIZE_CD = '" & "23" & "'"

    Dim cmd As New SqlCommand(strSql)
    Dim intCount As Integer = cmd.ExecuteNonQuery

と、SQLの文字列結合で実行すると、コンマ数秒で結果が返るのですが、

(2)
    Dim strSql As String = "update TMX_ITEM"
    strSql = strSql & " set DEL_FLG = 1"
    strSql = strSql & " where SHOHIN_NO = @SHOHIN_NO"
    strSql = strSql & " and COLOR_CD = @COLOR_CD"
    strSql = strSql & " and SIZE_CD = @SIZE_CD"

    Dim cmd As New SqlCommand(strSql)
    cmd.Parameters.AddWithValue("@SHOHIN_NO", "12345")
    cmd.Parameters.AddWithValue("@COLOR_CD", "01")
    cmd.Parameters.AddWithValue("@SIZE_CD", "23")
    Dim intCount As Integer = cmd.ExecuteNonQuery

と、SQLパラメータを使用すると、結果が返るのに５秒程度もかかります。
where句の条件項目がテーブルの主キーなのですが、
インデックスが使用されずにフルスキャンされている様です。

文字列結合はエスケープ処理やセキュリティの問題があるので、
SQLパラメータを使用する方向で開発すべきと思うのですが、
主キー指定で５秒もかかるようでは使い物になりません。

この様な処理速度の遅さは、SqlCommand.Parameters の仕様で致し方無い事なのか、
何かしらの対処方法が有る事なのか、情報をお持ちの方は御教え願います。