I have just made quick test for VFP Free Table with 203K records (volume=32M). The results are not so bad, especially for old-famed DELETED tag.

Set Deleted OFF ON

Simplest Query 0.27s 29.8s
w/out DELETED tag

Simplest Query 0.22s 0.16s
with DELETED tag

Complicated Query 13.6s 13.5s
with DELETED tag

So, DELETED tag looks OK. I didn't test SCAN,LOCATE but to my opinion nobody should use these commands for user-interactive operations on high-volume data (at least me not!).
All this stuff related to SET DELETED is pretty old but anyway from time to time it can really terrify people.