>Have tried all those thing. As Sergey said, packing the table is the only feasible option.

Sorry, won't believe that (let me be ignorant please).
One things though :

We don't use the FOR NOT DELETED() at all, and instead use the "technique" of changeing the key-value to a value which will be at the bottom of the table (index) always. Sorry for the mis-info, and Sergey is right. But, not on the impossibilty to solve this "feaseable" without Pack.
I am 100 % sure your problem can be avoided by the means we use ourselves (too keen on performance ...;) However, this involves some more, and is hard to explain in brief (that's why I didn't);

In general it comes to not allowing VFP to reach a deleted record ever.
This is what it comes to :

Assumed that a key is replaced with a high value at the basis (we use ~~) :

When using a loop like DO WHILE NOT EOF() etc, and an index is active (a Seek preceedes the loop) a SKIP within the loop looks as follows :

*** An existing (actual) record is the base ...

nSkipAmount = 1               && As the example. Could be -1, +100 etc.

IF nSkipAmount > 0            && Deleted records can't be upwards in the table.
  SET DELETED OFF
  SKIP nSkipAmount
  IF DELETED() AND NOT EOF()  && ... OR any other rejection on the key-value.
    SEEK "~~~~~~ ~~~~~~"      && Enforce EOF() -> can never exist.
  ENDIF
  SET DELETED ON              && The standard.
ELSE
  SKIP nSkipAmount            && Upwards.
ENDIF

Indeed, this can only work when you can interfere at the Skip, which Scan and Locate can't. Note that you may draw the conclusion that the Scan/Locate won't encounter deleted records anymore within the existing ones, and the replace of the key would be sufficient. But it's not, because of after the last existing record you will be doing a Skip, and you're in trouble again.

When you shoot a hole in the above again, I already anounce that we have some more in our framework around this, and which involves record #1 which is reserved for related manipulation ...

Whether you like this solution ? the execution of it is obviously slower, but as you already can guess, you win always once you have a fair amount of deleted records in the table.

Note : We have users who just never (read : for many years) pack their tables, comprising of real dynamic data (and millions of records).
We have this working for 15 years now, and back then (FoxBase+) it was really necessary. But obviously it still is, once you have enough deleted records to disturb you.