O que devo fazer para acertar o índice, considerando-se que minha aplicação é multi-usuário e que, a rotina de verificacao deve ser automática (feita
pela propria aplicacao).

Se você já tiver uma rotina de indexação sugiro que, no VFP, você dê um:

Validate Database Recover

Depois disso execute a rotina de indexação.

Sugiro, também, que você altere sua rotina de indexação pra ela apagar e recriar o banco de dados e os arquivos .CDX
A rotina de indexação que tenho faz assim:

1. Apaga o banco de dados
2. Apaga os arquivos .CDX
3. Varre todas as tabelas removendo o link ao banco que foi apagado
4. Adiciona todas as tabelas ao banco
5. Executa a Indexação

Prefiro, já de cara, excluir o banco de dados, pois o problema pode ser nele - antes de excluí-lo tenha certeza de que terá condição de recriá-lo - observe que, nele, pode haver StoreProcedures e outras coisas mais.