Assunto tenso. CEPs deveriam ser abertos, mas não são.
Pelo que sei o correio é uma entidade privada, só que em alguns casos foi considerado como publica porque ou faziam isso, ou ele poderia ter quebrado ou falido quando começaram a haver certos processos. E, no caso do CEP, parece que é até patentiado, e desde 2005 os correios passaram a criptografar a base de dados que vinha em um CD que vendiam que continha a listagem completa e atual dos CEPs. Por mais que seja acessível quebrar e obter os dados do CD atual, eles deixam claro que para você fazer isso, você deve entrar em contato com um setor especifico do governo, e orçar um pagamento para poder usar a base de dados de uma forma constante. Ja liguei pra eles tempos atras, e, é algo do tipo um representante vai na sua empresa pra discutir valores. Então pelo jeito não é algo trivial ou barato pra se pagar por mês. Então, fora de cogitação liberar isso de forma gratuita.
Qualquer grupo que quiser bater de frente em cima dessa questão de CEPs tem meu apoio.