Did you try to use non-cluster index?
>
>Yes we made the delete without sp_execute and we also change the Delete for a select and studied the execution plan and we have clustered index seek.
>
>From studying the execution plan, it looks like our problem come from updating the clustered index.
>
>For each row, 76% of the cost is for updating the indexes.
>
>We already tried to drop the cluster index but removing the indexes was even slower.
>
>What else can we try?
>