(1) Make sure that all indexes are marked "maintained." If not they immediately are considered "out of date."
(2) Make sure that all tables related to this one have the same "table language." If, for example, table-X is French and table-Y is US_ASCII, you'll always have problems.