I imagine it could be something like your index was very fragmented before one delete operation but not before another. How fragmented was the clustered unique index? You could see if there is still a difference in runtime after doing a rebuild on all indexes before the delete with something like ALTER INDEX ALL ON blah REBUILD
What options did you use when creating your unique clustered index (specifically what are the following set to: PAD_INDEX, STATISTICS_NORECOMPUTE, SORT_IN_TEMPDB, IGNORE_DUP_KEY, ALLOW_ROW_LOCKS, and ALLOW_PAGE_LOCKS)?