Deadlock

A deadlock is different to blocking, which is what I think you mean when you say that " ... The update SPs are fairly simple and should update fast enough to avoid a deadlock [Block] ..."
A block is not a deadlock, while a deadlock is a special kind of stalled block.A deadlock doesn't time out. SQL finds deadlocks, chooses a victim and kills it, allowing the other transaction to proceed - hopefully before it times out.
So what is a deadlock. It is a mutal thing, where generally two processes each have a resource, and want a resource that the other has (and like kids, wont budge!)
What causes deadlocks is insert/update (generally) code, that accesses the tables in different orders.
If all transactions update tables in the same order, then you cannot have deadlock. One transaction may need to wait for the other, but they won't both be waiting on each other.
To see a little more, run these tracesdbcc traceon( 3604 )dbcc traceon( 1204 )
You will need to do this each time the server restarts.
Now in the SQL Error Log, you have far more details from both processes.
C:\Program Fiiles\Microsoft SQL Server\MSSQL\LOG

Deadlocks aren't caused by people/systems accessing the same data at the same time. They're caused by situations where processes cannot resolve locks.
For example, process A has to lock table X, and then lock table Y, while process B has to lock table Y, and then table X. If A has a lock on X and wants a lock on Y, but B has a lock on Y and wants a lock on X, neither one can finish, thus a "deadlock" occurs, and SQL kills one of them.
The main way to solve that is to make sure that processes access and lock data in the same sequence as each other. No deadlocks that way.
I'd definitely analyze the deadlocks, find what's causing them, and fix that, rather than just taking the "nolock shotgun" and hoping you hit something with it. Using nolock as a solution for deadlocks is just asking for dirty reads and junked up data. Lots of people are taught to use nolock for this kind of thing, but aren't made aware of the fact that it can result in serious data problems.
For example, user A takes a look at row 3 of table X. Meanwhile, process B updates that row, but user A never sees the update, because of nolock and such. So user A updates the row, overwriting what process B did. Now, is that row of data correct? Process B's update is gone, as if it had never been done, and user A may have wanted a different update than the one he did, if he knew the data was being changed by process B. It can make a big mess.