Why do MySQL MyISAM table indexes go out of date?
This is only a guess but here it goes...
The only way I know that a PRIMARY KEY for a MyISAM table would be OK and all secondary indexes be out-of-date would be under this unique circumstance:
Running this
ALTER TABLE mytable DISABLE KEYS;

and forgetting to undo it with
ALTER TABLE mytable ENABLE KEYS;

When you disable keys, the PRIMARY KEY and all UNIQUE keys are unaffected. When you enable keys, all secondary indexes get rebuilt.
According to MySQL Documentation on ALTER TABLE:

If you use ALTER TABLE on a MyISAM table, all nonunique indexes are created in a separate batch (as for REPAIR TABLE). This should make ALTER TABLE much faster when you have many indexes.
This feature can be activated explicitly for a MyISAM table. ALTER TABLE ... DISABLE KEYS tells MySQL to stop updating nonunique indexes. ALTER TABLE ... ENABLE KEYS then should be used to re-create missing indexes. MySQL does this with a special algorithm that is much faster than inserting keys one by one, so disabling keys before performing bulk insert operations should give a considerable speedup. Using ALTER TABLE ... DISABLE KEYS requires the INDEX privilege in addition to the privileges mentioned earlier.
While the nonunique indexes are disabled, they are ignored for statements such as SELECT and EXPLAIN that otherwise would use them.

SUGGESTION
First, make a copy of the table.
Try running
ALTER TABLE mytable ENABLE KEYS;

and see if it does anything. If not, run
REPAIR TABLE mytable;

Give it a Try !!!