>Please provide more details on the performance problem. I'd hate to rework my apps that use SET DELETED ON, and 10,000+ record tables are common.

Easy to test.

Use FoxPro Windows.
1. Create a table having 100000+ records
2. Create at least this tag INDEX ON DELETED() TAG DELETE
3. SET DELETE ON
4. BROWSE or SELECT * FROM table WHERE yourtagvalue INTO CURSOR TEMP
You're gonna get the result right away.

Now, do the same in Visual FoxPro 3 or 5. You'll end up with a wait time because of the SET DELETE ON which should not be use anymore.