Here are the tally's and I think they support Michel's theories;

I ran the following code in 2.6a and 5.0 against a table with 5,227,700
records, and index on comp_lot and DELETED()

CLEAR
SET DELETE OFF
? TIME()+' With Delete OFF'
mcount = 0
SCAN FOR comp_lot = "CRA"
mcount = mcount + 1
ENDSCAN
? mcount
? TIME()+' With Delete OFF'

LOCATE
SET DELETE ON
? TIME()+' With Delete ON'
mcount = 0
SCAN FOR comp_lot = "CRA"
mcount = mcount + 1
ENDSCAN
? mcount
? TIME()+' With Delete ON'

2.6a produced
07:00:30 With Delete OFF
7524
07:00:38 With Delete OFF
07:00:38 With Delete ON
7524
07:00:38 With Delete ON

5.0 produced
06:54:38 With Delete OFF
7524
06:54:46 With Delete OFF
06:54:46 With Delete ON
7524
06:55:47 With Delete ON

Results indicate 2.6a and 5.0 are equal with Delete OFF
With delete ON 2.6a out performs 5.0. Set Delete does make
a difference.