The following query uses an index (see desc below)

select id,ts from messages where to_mid=114744 and mode='N' order by ts DESC;

it takes (first run) more than 20 sec! (2nd run and any run after takes less than 1/2 a sec > cached)
This query list all new messages in an inbox on a site.

the messages table structure:
CREATE TABLE `messages` (
`id` int(11) NOT NULL auto_increment,
`from_mid` int(11) NOT NULL default '0',
`to_mid` int(11) NOT NULL default '0',
`subject` varchar(200) NOT NULL default '',
`body` text NOT NULL,
`mode` char(1) NOT NULL default '',
`reply` int(11) NOT NULL default '0',
`flagged` char(1) NOT NULL default '',
`ts` int(11) NOT NULL default '0',
PRIMARY KEY (`id`),
KEY `from_mid` (`from_mid`),
KEY `to_mid` (`to_mid`),
KEY `ts` (`ts`)
) ENGINE=MyISAM AUTO_INCREMENT=20529343 DEFAULT CHARSET=latin1;

an explain shows:
id: 1
select_type: SIMPLE
table: messages
type: ref
possible_keys: to_mid
key: to_mid
key_len: 4
ref: const
rows: 5908
Extra: Using where; Using filesort

I tried it on 5 different servers, all with nice new hardware (2 cpu, 4 cpu, ton of ram, mysql4, mysql5, etc - all are not busy server ; i.e doing no other queirs nor serving anything).
The table have 15million records. its file sizes are: MYD=11G MYI=615M

First I thougt it is the 'order by' which explain say 'Using filesort', but I did a query for another account with no sort, and it took long time too.

the funny thing is that at this time, this mid have no new message, yet this is an execution:
mysql> select id,ts from messages where to_mid=114744 and mode='N' order by ts DESC;
Empty set (20.00 sec)
and here is one with no sort for a smaller account (that is why is a bit faster):
mysql> select id,ts from messages where to_mid=949245 and mode='N';

+----------+------------+
| id | ts |
+----------+------------+
| 19772336 | 1220576413 |
| 19654200 | 1220387595 |
| 19596893 | 1220296600 |
+----------+------------+
3 rows in set (16.02 sec)

Why it takes so long? How can I do a simpler query than that? Is this what MySQL can do with big tables?
thanks for any input.