O problema era hierarquia. O site estava buscando pelo CEP primeiro dentro de todo o Brasil, e como encontrava, informava as opções de entrega para Brasil. Após colocar a opção limitada por faixa de CEP na primeira posição da lista de regiões de entrega, o site voltou a apresentar as opções corretas.
