Have you actually looked at the contents of the CDX file. I used to have a bad habit of creating indexes on the fly and fogetting about them. Another thought, is it possible that the hard drive is badly fragmented. I'm sure you have gotten many suggestions and are probably sick of them by now. If you have the disk space you might try copying the dbf to another location without the indexes and them recreating them at the new location.
A problem is a problem only as long as it has a possible solution. Lacking that, it becomes a FACT!