Oracle 11g delete by unique key slow
Delete is a DML command and stores the data in redo log till the delete operation is committed.
 This means that if data to be removed by delete is slightly large[even though search time is less] it will take longer time as it will move data to redo log.

So may be the instance when your operation took longer large no. of rows were being deleted to many queries might be writing to redo log.