Problem Designing Index

Hello,

I'm doing some select statements on my table that look like:
SELECT * FROM table WHERE prod_num = '1234567' AND transaction_timestamp >
'2007-07-18 21:29:57' OR prod_num > '1234567' ORDER BY prod_num ASC,
transaction_timestamp ASC LIMIT 1;

I've added two indices one for prod_num and another transaction_timestamp.
This table has 151,000 rows and the above statement returns in less than a
millisecond. If I change the above statement from '>' to '<' it takes 8
seconds to complete. Prod_num '1234567' is towards the end of the 151k
rows. If i use a prod_num like '0000123' towards the front the problem is
reversed with '>' and '<'.

I tried adding a third index that uses both prod_num and
transaction_timestamp. The average performance at each end of the data for
both '>' and '<' improved but the problem wasn't resolved. Selects at the
end of the data with '>' conditions (Like the original statement) then
become broken and take 500 ms to finish, which is unacceptable for the
application.

I did analyze on the table with no effect.

Is it possible to design an index that can account for all the scenerios?
Thanks for any help you can provide.

-Alan