Strange Index Choice Behavior

[Ben Smith]

So I've had this query for a really long time (years):

SELECT message.val AS val, DATE_FORMAT(message.lastdt,'%M %D, %Y') AS d, DATE_FORMAT(message.dt,'%M %D, %Y') AS dd, message.id AS id, login.name AS name, message.title AS title, message.mestagid AS mestagid, mestag.name AS tagname, message.fileid AS fileid, people.name AS filename, message.emailto AS emailto, message.emailfrom AS emailfrom, message.emaildate AS emaildate FROM message LEFT JOIN login ON message.loginid=login.id LEFT JOIN mestag ON message.mestagid=mestag.id LEFT JOIN file ON message.fileid=file.id LEFT JOIN people ON file.peopleid=people.id WHERE message.accountid=1271 ORDER BY message.lastdt DESC LIMIT 0,20;

It has been crazy fast because it uses an index on accountid, lastdt of the message table (it only examines 20 rows). However, starting today it has been selecting the wrong index (the index it is selecting is on accountid,titlereversed,lastdt -- this index isn't new it's been around a year) but it is selecting it only when the accountid=1271. It accountid equals something other than 1271 it behaves properly. The problem is when it selects the wrong index it moves from taking 4 thousands of a second to 17 seconds. I've added USE INDEX in the mean time. But I would like to know why it has started to do this.