How about the last one? Is the record size really small?

Another thought - do you have current statistics on that table?

Can you post the exact output of the explain plan for the statement? Can you then add a hint to force the index and give us that plan as well?

- Chris