>>Are you running your update commands within one connection?
>
>At every hit, the same connection object is used for all SQL commands. So, each user has its own connection object. But, it will remain active for the hit duration only. So, during a hit, I can have 12 SQL exec commands, 4 updates and 3 inserts, for example. They will have all the same connection object.
>
>Do you see anything in there that could be related?

I just found an interesting article confirming my prior suggestion (which, I'm afraid, may not be applicable to your situation)

http://www.sql-server-performance.com/articles/per/deadlock_sql_2005_p1.aspx