Hmmm. Very interesting. Well, this is definitely the type of query that a *tight* index scan might be used (see
http://dev.mysql.com/doc/refman/5.0/en/tight-index-scan.html), and from the docs, I can't tell whether MySQL would indicate in the Extra column if it has chosen to do this. But, from what you're describing, it certainly sounds like the query optimizer has been tweaked to prefer this type of optimization, and in your case, it is negatively affecting the outcome.
Why don't we do this. Can you work on getting a mysqldump of your DB (if that's possible) and I'll try to contact someone who might be able to take a closer look at this? I'll have them post back here with advice on what to do next. (I'm thinking Edwin DeSouza...)
Jay Pipes
Community Relations Manager, North America, MySQL Inc.
Got Cluster?
http://www.mysql.com/cluster
Personal:
http://jpipes.com