JDBC Deadlock On Unrelated Records

Hi all,

I'm regularly getting the "deadlocked..you're the victim" message when two
threads work on a table at the same time via JDBC. The two threads don't
update the same records. I suspect the cause is related to index or page
locks, and/or the fact that the UPDATE statements are doing table scans
because there's no index on the primary key (no, I'm not the DBA!)

1. Thread A selects some records to play with:

select top 50
I.*,M.this,F.that
from APInvoice I
inner join M ...
inner join F ...
where I.CmStatus = 'O'

(There is an index on CmStatus + another column called CmTime, so I expect
this index to be used. It's also the only index on the table.)

2. Gradually, within the same transaction that did the SELECT, thread A
updates all 50 selected records:

update APInvoice
set CmStatus = 'S',
CmTime = getdate()
where itemid = (an ID number from the select in step#1).

(There is no index on itemid, which is the unique primary key column)
(There is an index on CmStatus + CmTime).

3. While step#2 is running, thread B starts and does a single update.
That's all that thread B does:

update APInvoice
set CmStatus = 'C',
CmTime = getdate()
where itemid = (an ID number that is NOT in the list of records being used
by thread A)

I consistently get deadlocks whenever thread A & B run at the same time.

To resolve ths problem, I'm looking at the following actions:
1. Create a unique primary index on ITEMID.
2. Add an "(UPDLOCK)" or "FOR UPDATE" to the SELECT statement.

Are these reasonable things to try? Is there something else I should be
doing?