Olá,
Ivo, o Access a partir da versão 2000 passou a utilizar um sistema de codificação de caracteres diferentes, chamado Unicode. Antes ele usava o padrão ASCII de 16 bits padrão, agora, como Unicode, ele tem suporte a uma gama maior de caracteres internacionais sem necessidade de mudanças de página como no ASCII. Bom, isso para a Microsoft é ótimo, mas para nós não, pois o Unicode usa 32 bits, ou seja o dobro. Você já deve ter percebido que ao compactar um banco ele diminiu para cerca de metade do tamanho ocupado antes de compactar (em alguns casos mais, dependendo se houverem ou não exclusões de registros ou objetos de dados).
Resumindo, o seu banco continuará a crescer rapidamente e você deverá proceder a compactação de tempos em tempos, de acordo com o volume de informação armazenada no banco de dados. A maioria dos bancos de dados hoje cresce rapidamente. O SQL Server e o Oracle também. A maioria está adotando o padrão unicode também.
Agora, veja que se o Access está "zerando" o contador dos campos autonumeração, isso pode significar um problema na estrutura do seu banco. Eu não gosto de campos autonumeração, pois das poucas vezes que eu usei ele me deu problemas com grandes quantidades de registros, como gerar número duplicados ou pular seqüências, um problema relatado pela própria Microsoft.
Enfim, a única solução que eu veja para você é dividir o seu banco de dados. Você pode usar a solução proposta pelo Daniel, embora eu preferisse usar outra opção se estivesse no seu lugar. Eu criaria um outro banco, ou outros bancos para registros "obsoletos", ou seja, registros que tivessem mais de x tempo dentro do banco de dados. Esse tempo seria determinado por uma estimativa de uso de dados mais antigos. Eu não seu qual seria esse tempo para você, mas basicamente a minha idéia é remover do banco principal os dados obsoletos e armazená-los em outra base de dados, tipo um arquivo morto. Aí o seu programa poderia fazer a busca no arquivo morto caso não encontrasse o registro no banco principal e apenas depois de avisar ao usuário e pedir confirmação.
Um Abraço,
Sandro.