How to force SQL server to use row locking for specific update/delete statements
I know you said with (rowlock) did not appear to be working
Are you including a &lt;> for the set as then it will avoid an update lock  

update table with (rowlock) 
set col1 = 1 
where col1 &lt;&gt; 1


with (tablock holdlock) might fix deadlock
as then you only have one update at a time
it is worth a try  

Are your transactions updating tables in the same order?