>Michel, generally, a "one by one, for next loop" is not recommended. (I won't say "never", but as a general rule, it's better to delete rows as a set-based operation)

Yes, I know. This is why I am trying to find a resolution so to avoid using that route. :)

>- Can you identify the fragmentation level of the table/indexes? (I can give you some code to check for it, if you would need it). I'm not saying it's necessarily what's going on here, but I see many client databases that suffer serious neglect in the area of fragmentation

I didn't know we could control that. Yes, if you have some code, I would be happy to check something in regards to it.

>- How often are the indexes rebuilt on the affected tables?

Never

>- How often are database statistics updated on the affected tables?

I wouldn't know anything about it. Do you have some information I need to follow so to obtain the related statistics?

>- Are the conditions for the deletes (and the concurrent queries that are locking up) effectively using indexes? (i.e. can you check the execution plans of all relevant queries to see if maybe the execution plan isn't as efficient as it could be)

The concurrent queries is an insert command. So, I wouldn't know what could be optimized there. As far as the DELETE WHERE clause, I can check that out. I will be back on this with more information.