Are you using triggers on the base tables? Is it possible that the deadlocks are caused by triggers stepping on each other?