I tried to log slow queries. Slowest queries are of this type for example:
select value from history_uint where itemid=23287 and clock<=1273669687 order by clock desc limit 2;
It selects many thousand lines, and takes several seconds to perform. Finally, it selects only 2 rows with LIMIT.
I propose that find this SQL query and restrict choice from clock.