Walter,

>> In my testing table of 1.900.000 records i've deleted about 19.000 records
>> and could not find any significant difference with or without the deleted() tag.

In this case the problem seems to be that the entire statement isn't optimized. Have you tried Sys(3054,1) to see the optimization level?

Markus