Why is my non clustered index causing this deadlock?

Question

I have an application that runs the following query in multiple parallel threads:

update Table1 SET Col1 = 'Some value' WHERE Order_ID = @orderID

Order_ID is NOT the primary key on this table, but the @orderID is different for each thread, this update used to run fine until a non-clustered index was introduced:

CREATE NONCLUSTERED INDEX MyIndex ON dbo.Table1 (Col2, Col3, Col4 ... Order_ID)
INCLUDES (Col5, Col6, Col7 ... Col1)

After this index was introduced, the following deadlock started occurring:

I considered the deadlock sequence presented on this answer, but I think if that were the case my deadlock should also happen without the index.

How could my index be causing this deadlock and how should it be fixed without complete removal of the index?

-- Edit -- This is the .xdl file saved by the SQL Profiler:

<deadlock-list>
 <deadlock victim="process145bf9d2ca8">
  <process-list>
   <process id="process145bf9d2ca8" taskpriority="0" logused="32184" waitresource="KEY: 18:72057594138460160 (edd8040a164e)" waittime="5008" ownerId="138282264" transactionname="user_transaction" lasttranstarted="2023-02-15T10:34:18.533" XDES="0x145b8c48428" lockMode="U" schedulerid="6" kpid="33688" status="suspended" spid="54" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2023-02-15T10:34:21.607" lastbatchcompleted="2023-02-15T10:34:21.603" lastattention="1900-01-01T00:00:00.603" clientapp=".Net SqlClient Data Provider" hostname="FRSWS55" hostpid="29140" loginname="sa" isolationlevel="read committed (2)" xactid="138282264" currentdb="18" currentdbname="ServerTestingP29140_DB3" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
    <executionStack>
     <frame procname="adhoc" line="1" stmtend="214" sqlhandle="0x020000001ba7e0312df94ebaf66af9aa789376b49f2de1750000000000000000000000000000000000000000">
unknown     </frame>
     <frame procname="adhoc" line="1" stmtend="214" sqlhandle="0x02000000625d920d3c88802b4f67ca779601eb8827479bde0000000000000000000000000000000000000000">
unknown     </frame>
    </executionStack>
    <inputbuf>
UPDATE Securities_Fund_Deals SET Market_Deal_Reference = &apos;[No Deal Ref]&apos; WHERE Securities_Orders_ID = 100002    </inputbuf>
   </process>
   <process id="process145d205d848" taskpriority="0" logused="37724" waitresource="KEY: 18:72057594138460160 (92097e2303df)" waittime="5306" ownerId="138285954" transactionname="user_transaction" lasttranstarted="2023-02-15T10:34:19.667" XDES="0x145ba19c428" lockMode="U" schedulerid="2" kpid="31776" status="suspended" spid="67" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2023-02-15T10:34:21.607" lastbatchcompleted="2023-02-15T10:34:21.603" lastattention="1900-01-01T00:00:00.603" clientapp=".Net SqlClient Data Provider" hostname="FRSWS55" hostpid="29140" loginname="sa" isolationlevel="read committed (2)" xactid="138285954" currentdb="18" currentdbname="ServerTestingP29140_DB3" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
    <executionStack>
     <frame procname="adhoc" line="1" stmtend="214" sqlhandle="0x020000001ba7e0312df94ebaf66af9aa789376b49f2de1750000000000000000000000000000000000000000">
unknown     </frame>
     <frame procname="adhoc" line="1" stmtend="214" sqlhandle="0x02000000435327051ac761ce938ca1fddda496271bb2f4a70000000000000000000000000000000000000000">
unknown     </frame>
    </executionStack>
    <inputbuf>
UPDATE Securities_Fund_Deals SET Market_Deal_Reference = &apos;[No Deal Ref]&apos; WHERE Securities_Orders_ID = 100003    </inputbuf>
   </process>
  </process-list>
  <resource-list>
   <keylock hobtid="72057594138460160" dbid="18" objectname="ServerTestingP29140_DB3.dbo.Securities_Fund_Deals" indexname="IX_Deals_Screen" id="lock14570081500" mode="X" associatedObjectId="72057594138460160">
    <owner-list>
     <owner id="process145d205d848" mode="X"/>
    </owner-list>
    <waiter-list>
     <waiter id="process145bf9d2ca8" mode="U" requestType="wait"/>
    </waiter-list>
   </keylock>
   <keylock hobtid="72057594138460160" dbid="18" objectname="ServerTestingP29140_DB3.dbo.Securities_Fund_Deals" indexname="IX_Deals_Screen" id="lock145b1c0fb80" mode="X" associatedObjectId="72057594138460160">
    <owner-list>
     <owner id="process145bf9d2ca8" mode="X"/>
    </owner-list>
    <waiter-list>
     <waiter id="process145d205d848" mode="U" requestType="wait"/>
    </waiter-list>
   </keylock>
  </resource-list>
 </deadlock>
</deadlock-list>

Answer 1

How could my index be causing this deadlock and how should it be fixed without complete removal of the index?

Because the plan must scan the entire index to find the rows with that @orderid. So each session has found an updated a row, but the other session needs to read that row to see if it has the target @orderid.