I don't believe another index will help, may even make it worse. However, do this:
SET SHOWPLAN ON
your DELETE statement
Check the showplan of the current delete. Make sure it is traversing the clustered index using the first 2 columns as keys. More than likely, you are deadlocking due to the # of non-clustered indexes on the table being maintained by the delete. It would seem that under concurrent activity, the deadlock will be due to someone else banging into your delete as it holds the locks on the pages of the NC-Indexes while the delete occurs.
One thing not mentioned is - does this table have a delete trigger on it doing anything else?
Two solutions - one is to make the table ROW or DPO locking so that latches are used on the NC-Index pages and not logical locks.
Next, you really do not need the non-clustered index on
ID_A, ID_B => nonclustered
since your clustered index already has the same two leading columns and this is redundant (do you really need it for a covered index?). At a minimum, removing this index would allow for you to have less maintenance happening on NC-Indexes and possibly help (though not 100%) the deadlocking.
Deadlocks in ASE are generally not 100% avoidable and so any of the code you write against ASE should do error testing of any SQL that is sent into it for deadlock and retry the unit of work. Don't code stored procedures which could deadlock 1/2 way through and fail. Always code to expect deadlocks even if they never occur.
I tried extra index, and as you said, it was still deadlocking. Retry loggic is in there, and basically out of 2100 times it deadlocked 30 times. Usually passes on second itteration. There are no delete triggers on the table.
For now, I'll just let it be, and do more testing with the showplan. The trigger you pointed out is definitely redundant.