Just for curiosity, i tried this having only 1000 records instead of 3553 in the tables CLIENTES. :

select first 20 * from LISTA_CLIENTES where (CLIENTE like 'crist%'
or MORADA like 'crist%' or LOCALIDADE like 'crist%' or CLIENTE like
'crist%' or PAIS like 'crist%' or PAIS_NOME like 'crist%' or
TELEFONE like 'crist%' or EMAIL like 'crist%' or CONTRIBUINTE like
'crist%' or COND_PAGAMENTO_DESCRICAO like 'crist%') order by CLIENTE

It took 17 seconds to perform the query and return only 2 records. Note that i created an index for each field in the where condition.

Unfortunately, still no improvement in performance.