Now this is an interesting thread, reading some of the other problems i am shocked that the companies had trusted these guys with the databases...

My two pence worth on the subject.

We have several tables with 20 Million + rows...the thing is that with stats the optimizer makes a calculated guess to determine the correct path for execution, do note that i said a calculated guess. Its not entirely correct. It takes into account several things like for eg:

sort_area_size
db_file_multiblock_read_count
optimizer_index_cost_adj
optimizer_max_permutations

What sort of values do u have for these? The third one is specially useful if the indexes are not used in your queries. Set it to a lower value to force index scan rather than full table scans.

Hope this helps and get back to me on your optimizer behaviour findings.

Cheers,
Ali