Used EXPLAIN, have indexes - query still surprisingly slow

[developer]

I have the following query that takes anywhere from 1 to 3 seconds
to run. I would expect it to run in less than 1/2 a second (and
I really need it to do so). I've added the appropriate indices
and tried EXPLAIN and ANALYZE; but, I'm not getting anywhere.

SELECT message.id
FROM message, message_thread
WHERE message.id = message_thread. message_id
AND message_thread. thread_id = SOME_CONSTANT_N UMBER

where SOME_CONSTANT_N UMBER is an integer literal, like 16400 (and no,
I'm not putting quotes around the number).

Here are the two tables involved:

message table
------------------------------------------------------------------
Field Type NULL Key Default Extra
------------------------------------------------------------------
id int(11) PRI NULL auto_increment
msgtype_id int(11) MUL NULL
content blob YES
precedence varchar(255) YES
message_thread table
------------------------------------------------------------------
Field Type NULL Key Default Extra
------------------------------------------------------------------
id int(11) PRI NULL auto_increment
message_id int(11) MUL -1
thread_id int(11) MUL -1
contact varchar(255) YES

The message table has 1,117,213 records and the
message_thread table has 2,563,893 records. At most, each query
will return 200 records.

Here is the output of the explain function (turned sideways):

---------------------------------------------------------------
table : message_thread message
---------------------------------------------------------------
type : ref eq_ref
---------------------------------------------------------------
possible_keys : thread_id, PRIMARY
message_id
---------------------------------------------------------------
key : thread_id PRIMARY
---------------------------------------------------------------
key_len : 4 4
---------------------------------------------------------------
ref : const message_thread. message_index
---------------------------------------------------------------
rows : 200 1
---------------------------------------------------------------
Extra : Using where Using index
---------------------------------------------------------------
This is running on a 2.2 GHz Pentium 4, NTFS File system,
MS Windows 2000, MySQL 4.0.18. Each table is an InnoDB type.

I've tried a combined thread_id/message_id index in the message_thread
table; but, that did not seem to help at all.

Any help would be appreciated.