The absence of "Using index" does not mean that no index was used. Instead it means that the data was not consulted because all the necessary fields are in the index.
This indicates that an index was not used:
mysql> EXPLAIN SELECT ... \G
*************************** 1. row
id: 1
select_type: SIMPLE
table: foo
type: ALL <--
possible_keys: msg
key: NULL <--
key_len: NULL
ref: NULL
rows: 17499
Extra: Using where
Another item... In InnoDB, the PRIMARY KEY is always "clustered" with the data. So, a table scan of the data and an index scan of the PRIMARY KEY do essentially the same thing, and have to walk through all the data (except maybe some BLOBs).
Some of your cases fall into this non-distinction between scanning the PK index and scanning the data. The EXPLAIN looks different, but the effect is not.
DISTINCT _may_ require an extra pass. Possibly the optimizer can realize that the data being SELECTed is all UNIQUE (that includes PRIMARY KEY). Possibly it has to make an extra pass over the data, either sorting it or using a hash table. This can be very much like GROUP BY. Sometimes, the extra sort pass is avoided by using the index, or folding in with the ORDER BY. In your cases, DISTINCT probably needed the extra pass.