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.