This is a quote from the isolation link I sent about Read-Committed Isolation:
In SQL Server 2005, you can also minimize locking contention while protecting transactions from dirty reads of uncommitted data modifications using either:
The READ COMMITTED isolation level with the READ_COMMITTED_SNAPSHOT database option set to ON.
The SNAPSHOT isolation level.
READ COMMITTED
Specifies that statements cannot read data that has been modified but not committed by other transactions. This prevents dirty reads. Data can be changed by other transactions between individual statements within the current transaction, resulting in nonrepeatable reads or phantom data. This option is the SQL Server default.
The behavior of READ COMMITTED depends on the setting of the READ_COMMITTED_SNAPSHOT database option:
If READ_COMMITTED_SNAPSHOT is set to OFF (the default), the Database Engine uses shared locks to prevent other transactions from modifying rows while the current transaction is running a read operation. The shared locks also block the statement from reading rows modified by other transactions until the other transaction is completed. The shared locks are released when the statement completes.
If READ_COMMITTED_SNAPSHOT is set to ON, the Database Engine uses row versioning to present each statement with a transactionally consistent snapshot of the data as it existed at the start of the statement. Locks are not used to protect the data from updates by other transactions.
When the READ_COMMITTED_SNAPSHOT database option is ON, you can use the READCOMMITTEDLOCK table hint to request shared locking instead of row versioning for individual statements in transactions running at the READ_COMMITTED isolation level.
By looking at the sql debug output, isn't the deadlock occurring between two threads executing the same update query?
Deadlock is caused by two process trying to aquire the same resource. This may or may not be the same query.
SQL has certain functionality to remove deadlocks automatically. This is why you begin to process after a period of time. The deadlock victim is the process that is the least expensive to rollback.
You could try to change the read_committed_snapshot option to on to reduce contention. You should note that the transaction will be unaware of any of transaction making an update at the same time.