Muito obrigado carlessoflu, lendo o código eu vi que ambas as consultas que eu utilizo usam a consulta do IBGE para pegar o código da cidade, então fiz o que você falou. Inclusive alterei a consulta do CNPJ para pegar o código da cidade através da consulta do CEP na qual eu configurei para consultar em mais de uma URL caso faltar algum dado que eu preciso.
A consulta as vezes pode ficar mais lenta caso não trazer o código da cidade por exemplo, por causa de em seguida gerar uma nova consulta em outra URL, mas assim eu aumento as chances de sempre me retornar o que eu preciso.
A respeito do motivo de parar de funcionar a consulta no IBGE, como não sei como funcionava antes, eu acho que o site que era feito a consulta antes foi totalmente alterado, mudando as tags de consulta e de retorno. Como não sei lidar bem ainda com questão de envio de dados e verificação de retorno de sites/urls em Delphi eu preferi fazer essa mudança mais simples nas minhas consultas.