Se você teve problemas para salvar o CPF apenas com zero, provavelmente você não está salvando ele como uma string do CHAR ou VARCHAR. Afinal, essas colunas terão a codificação de texto escolhida para o banco/tabela (charset).

O que remove zeros a esquerda é o processo de conversão para inteiro. Não sei como o seu algoritmo foi construído, tenho pouco a opinar. Porém, acredito que essa conversão devia acontecer em algum momento.

Não existe nenhum problema em salvar o CPF formato, inclusive. E a estratégia com CRC32 auxilia ainda mais nesse processo melhorando a performance. Vamos supor que você tenha a string com 015.599.874-80. O CRC32 dela é um decimal 1947733562.

Quando você for inserir, você insere formatado (015.599.874-80) com o CRC32 calculado. E quando você buscar, você irá localizar o CRC32 primeiro (1947733562) e depois o CPF. O ponto é que o CRC32 sempre será o mesmo para a mesma entrada, então não importa a entrada. Funciona como um hash.

Já o armazenamento, é importante escolher o tipo de coluna correto para não enfretar os problemas de salvamento que mencionou.