I think you're right. Indices must have the expression you're trying to match and must know what record that match goes with. I don't understand the part about a funny three-byte integer format. One would think that the offset or record pointer would have to be more than three bytes (actually four bytes would be fine) since three would give a maximum 16.7 million different values. We know we can have tables with millions more records than that.
From what I've seen, I think most of the work takes place at the index level. Records are never fetched until all useful info has been read from the indices.
Rushmore does this even when it's not a good idea, and it's up to the developer to design the queries to limit this.
If you had tags on Name and Sex
SELECT * FROM MyTable WHERE Name = "Charlie " AND Sex = "M"
would probably run better as
SELECT * FROM MyTable WHERE Name = "Charlie " HAVING Sex = "M"
or even
SELECT * FROM MyTable WHERE Name = "Charlie " AND UPPER(Sex) = "M"
since the last 2 are not fully optimized...which is better...because of the traffic generated by the badly skewed tag where "M" and "F" dominate the expressions.

The LOCATE with a FOR and SET ORDER TO Something is still wrong in that it shouldn't care about the active tag. It's as if the old code before Rushmore optimization didn't quite all get examined.
>
>SET SPECULATE ON
>
>My understanding of the theory is that an entry in an index tag consists of two parts: the key value and the record number. I've been actually reading the hex dumps of some CDXes in my time, and this seems to be the case, though the record numbers were laid out in a funny three-byte integer format. Now the only reasonable scheme, IMO, would be to have the bitmap represent the record numbers in the physical order, regardless of Set Order. The bitmap is manipulated according to the logical conditions in the Where or Four clause of the command, and the bits are set on or off depending on them, always in physical order.
>
>Now the difference would come when the bitmap is finished, and the records should be retrieved. If there's no order set, the records can be retrieved sequentially, as they are laid out in the bitmap. If they're not, the active tag should be consulted in a reverse manner (or any other unnatural manner) to fetch the records based on the bitmap in the set order. It may require consulting each entry in the current tag to see if it's contained in the bitmap, or pulling down all the records in their physical order and sorting them to the current order.
>
>So, the difference appears _after_ the bitmap is created.
>
>SET SPECULATE OFF