1) Verifique se você tem um índice no carimbo de data/hora
2) Supondo que id_tick seja tanto a PRIMARY KEY quanto o Clustered Index, e supondo que id_tick seja incrementado em função do tempo (já que você está fazendo um MAX)
Você pode tentar isso:
SELECT id_tick, price, timestamp
FROM EURUSD
WHERE id_tick = (SELECT id_tick
FROM EURUSD WHERE timestamp <='2010-04-16 15:22:05'
ORDER BY id_tick DESC
LIMIT 1)
Isso deve ser semelhante ao desempenho do janmoesen, pois deve haver alta correlação de página entre id_tick e timestamp em qualquer caso