Low Cardinality of Index performing better than High Cardinality?
The between condition is short form for:

 ... range_from &lt;= $value 
 and $value &lt;= range_to


In this context range_from and range_to have an effective cardinality of 2, in range or out of range. 

Given your indexes the range_from needs to be searched for all values up to and including $value.  If value is close to the end the possible values, the number of records that need to be checked is quite high.  If you are looking for recent records, this is will be close to all the records.  

Using the index with the depot column first, far fewer records match the range_from value.  If you have 100 depots, you have 1% of the records to check compared to not using it.  Depots with few records will be faster than those with more records.  Your results on table A will vary depending on the value of $other.

In either case, the query could be completed within the index.  Without depot in the index, the query optimizer might decide to scan the table rather than the index.  Some SQL dialects allow a hint to the optimizer indicating the number of rows the query will match.  This can influence the resulting query plan. 

While you consider the cardinality low, from an optimization standpoint, it is quite high it reduces the number of index rows to be scanned by a factor of 100.

While the cardinality of the from_range may be high from a values standpoint. When running a range search it is of little value in searching for records.  For high values (which may be the most common case), it will match close to 100% of the records.  Its high cardinality, is of more use when running a range check of the form:

where from_range between $low and $high


The index may be more useful if the range columns are ordered range_to, range_from.