Hey, you are right!
Since my DELETE is not really deleting anything, I just RLOCKed the first record in the table from another session, and bingo!
When running my "slow" DELETE it shows "Attempting to lock..." message. When I Escape out of it, it continues on the rest of the records.

Sergei Berzniker says he'd consider this behaviour a bug, as it shouldn't attempt to RLOCK a record not being updated.
Come to think of that I am not so sure - it might be that "gray area" of uncommited changes, non-repeatable reads, etc for which the "big guys" like Oracle have transaction isolation levels (4 of them last time I checked). But VFP has to work with what it has.
For example, in my scenario, say I RLOCKed the record that should have been deleted. VFP however lets me Escape out of lock attempt and leave it alone. And it won't report an error (with certain SET REPROCESS of course).
On the other hand, maybe while it is RLOCKed, it is being changed so that it won't match the delete criteria, so it is probably a good idea to let me skip "uncommited changes".

Anyways, I wish somebody from MSFT clarified this. What do we do?