Are you sure it was actually using the index you expected? There are subtleties in index field order that can prevent the query optimizer from using an index that you might think it should be using.

One common misstep is having a table with columns like (id, user, date), with an index on (user, id) and on (date, id), then issuing a query like "... WHERE user = 1 and date > ...". There is no optimal index for that query, so the optimizer will have to guess which one is better, or try to intersect them. In this example, it might use only the (user, id) index, and scan the date for all records with that user. A better index for this query would be (user, date, id).

One of the more bizarre things we'd found in MySQL 5.something was that accidentally creating two identical indexes significantly slowed down queries that used it.

I wouldn't be surprised if you hit some sort of similar strange bug.