Desconheço o problema do FB com índices. Poderia anexar os links que você encontrou?
O que sei é que dependendo do tamanho e da quantidade dos índices, então realmente vai haver uma demora. Mas isso é natural, afinal a ideia dos índices é justamente consumir tempo antes fazendo o índices para diminuir o tempo da pesquisa depois.
Poderia executar um "gstat -a" no BD e postar o resultado? Talvez eu possa encontrar alguma coisa para lhe dar alguma ideia. Se puder também, nesse caso, coloque também o SQL que causa a demora.
EDIT: Desculpe, esqueci de pedir para fazer o acima com o BD em funcionamento. Não faça um backup/restore antes. Execute o gstat no BD em uso pelo cliente.