Believer may be a bit too strong, but I'm getting nearer to your opinion.
A few things we do know. When you do a Rushmorizable expression that is skewed in your favor (meaning the matches are a small part of the total pointers for that key), VFP in its wisdom doesn't have to read the entire portion of the CDX devoted to that index expression. Nor does it have to read up to the point of the match. It's doing that job much too fast. In your situation, when you say you set the order to the same tag as Rushmore is using, that isn't quite the same thing to VFP. In my testing your scenario, I saw the ORDER command cause the entire set of pointers to be read up until the matches from Rushmore--much more traffic than is necessary--and different logic than Rushmore. Thanks for your answers so far. They have helped answer certain parts of the puzzle.
If you indexed your table on a particular field, in other words had a CDX that contained only one tag, how long would it take to copy it from the network to your machine? I'm asking that just to clarify how fast can your machine can read the CDX into its memory. If you then used the table in SHARED mode and SET ORDER TO TheField, and did a locate to a record that is near the bottom of the index, you are saying that it may take 30 minutes to LOCATE the record, which seems to you, (and me too), like VFP is having to read the entire table, not just a CDX file. Right? I would expect your LOCATE to take the time it takes for VFP to read the entire CDX, which could be slow, but should account for the time you saw.
BTW, I don't have VFP 3.0, but 2.6 and 6.00.8 both seem to work the same way.

>Ahh... Starting to make a believer out of you... :)
>
>The really odd thing is that I can do a locate on an indexed field I already have set (which should be cached) and it's still slow.
>
>No, I haven't indexed on Deleted().
>
>The tables are all opened in Share mode, but nothing was being added to the tables during any of the tests. Also, I think it is important to stress that I was working with tables of 10 million records+. I didn't notice it on even fairly large tables, but when you start working with millions of records it becomes more obvious.