When acquiring locks in the same order is not possible or not feasible.

I've been able to work around this in some tough cases by adding a select statement with a locking hint upstream, to force the order. (this violates your rule about no hints, though :-) For example, if it's important to lock a row in table A and then delete from table B, and then delete from A, it's possible to select from A with locking hints to "reserve" the parent row, then delete children from B, then the parent from A. A little ugly, but it works as a last resort...

Merril,

In the scenario which you are describing, you do not need to acquire locks on all objects - locks on just one, on the parent row, is enough. If I understood you correctly, that is exactly what you are doing: getting an exclusive lock on one resource. As long as you are acquiring that one exclusive lock in the same way in all your modules, you are fine, and your approach is equivalent to sp_getapplock. If, however, you are using different commands to get it, you still may get deadlocks.

This is the whole point of my post: instead of trying to maintain the same order, serialize on a single resource.

Alex, have you used the technique of capturing the 1205 message and re-trying the transaction?  Admittedly, I have never had the need for it but was curious if you have and if you've found the results less than ideal.

Right, I've read that one before.  I guess my fundamental question is whether a mutex lock really makes sense or should you just make an attempt at re-trying at least once before giving up.   The way I look at it, if you fail on a 2nd attempt or subsequent attempts, you likely have a larger issue somewhere else.