Any idea how many rows are normally deleted by your delete process?

If it's more than about 5000, then you're likely to be getting table locks due to lock escalation, in which case it may be worth considering amending your delete to remove the records in batches of, say, 4000 which should at least prevent this issue