Navegando na internet por um serviço de consulta de CEP descobri que os Correios disponibilizaram um WebService com vários métodos, realizei alguns testes e realmente funciona muito bem e com um tempo de resposta satisfatório.
Não irei me aprofundar em como consumir o serviço, mas estou disponibilizando abaixo a URL para que você possa fazer testes usando o SOAPUI, WCFteste ou qualquer outro programa de sua preferência.
Método Testado: consultaCEP
URL: https://apps.correios.com.br/SigepMasterJPA/AtendeClienteService/AtendeCliente?wsdl
Imagem dos métodos disponíveis para consulta.
Atualização 23/11/2017
Navegando pela internet estudando mais sobre o assunto achei um ótimo poste do André Alves Lima, segue abaixo link.
Clique aqui para acessar.