Hi again- sorry, I have been away taking a long weekend.
Yes I see some similar behaviour in a weather database I have, usually I do not have some of the columns indexed. I have 600+ MB numeric data. From what I see I have quite a bit of same data in the columns so the indexes for the columns are not very effective - If I involve the primary index which only has uniques it is very fast indeed.
I came to this conclusion after SELECT count(column) WHERE .... for both of the critera. It is also much faster with just one criteria even with order by.
This makes me believe that both the merge of the columns (between the temporary memory tables) and the order by takes its toll. In my case I also found that LIMIT 50 did not improve much if the both column criteria matched lots (25,000 columns 64000 recs) each.
So, apparently it does not use the indexes under some circumstances, which is indicated if you have a look at possible_keys in the reference manual. It also refers to FORCE INDEX and other ways.
One difference is I have InnoDB (for using transactions), and you have MyISAM - For InnoDB there is a chance of using the primary index, with every index - since you use * in the select. But I haven't had time to check out any improvements.
Since I mainly used SQL Server at work before, now at early retirement I decided for my weather project to use some things that were already made with other tools that included MySQL - I was thinking of using the implementation of NULs in MySQL, which differs quite a bit from what I was used to do. My thought being - a possible faster creation of the temp memory table. But my time is too limited right now to experiment with this.
Time to go to bed now, here in Europe - Hope someone else decides to take part in this, because it looks like you have a problem that I might also hit later on.