Mysql used key changes between two consecutive EXPLAINs
It sounds like the table is on the cusp of a cutover for the query optimizer between the estimated total rows and estimated rows being looked up.

The use/ignore index syntax exists for situations like this.

The pitfall to this approach is when the table dynamics change in the future such that it's really not the best choice.