Optimizing query that spends a lot of time in "statistics"

I've got a very simple query ("SELECT a,b,c FROM mytable WHERE d=foo
AND e=bar"; d and e are part of the primary key) that I'm executing
tens of thousands of times in a particular application. The primary key
is too big to fit in the key cache (it's about 64G, the table is really
huge). I've noticed when I do a SHOW PROCESSLIST that the query is
spending most of its time in 'statistics'. What can I do to reduce the
time that this query takes? I tried using FORCE INDEX but that didn't
seem to change anything. Would prepared statements help? Would
upgrading from MySQL 4.1.16 to 5.x help? Would splitting the table into
multiple tables help? Basically, I'm just not sure how best to attack
this problem.

Tom