Você está tendo um problema quase universal com os Contatos do Google. Parece que o Google armazena contatos em um banco de dados e duplica o contato sempre que ele é alterado e marca a versão antiga do contato para que ele não seja exibido no site. Não consegui encontrar nenhum software de sincronização que possa diferenciar entre os contatos válidos atuais e versões anteriores e contatos excluídos. Parece que, em algum momento, o Google resolveu remover os contatos antigos, mas parece que leva muito tempo, algo como 90 dias.