Rejeição 259: CNPJ da consulta não cadastrado como contribuinte na UF
Descrição oficial da SEFAZ: CNPJ da consulta não cadastrado como contribuinte na UF
O que significa
A consulta cadastro foi aceita, mas o CNPJ pesquisado não existe como contribuinte de ICMS naquela UF. O número é válido; o cadastro estadual é que não está lá.
Por que acontece
A empresa não é contribuinte de ICMS naquele estado (pode ser prestadora de serviço, do Simples sem IE, ou só ter inscrição em outra UF). Também ocorre quando a consulta é feita na UF errada, ou quando o CNPJ é de filial e a inscrição está em outro estabelecimento.
Como resolver
Confirme em qual UF a empresa tem inscrição estadual e consulte nessa UF. Se ela realmente não é contribuinte, isso não impede a operação: a NF-e deve sair com o indicador de IE do destinatário como não contribuinte ou isento, conforme o caso, e sem IE preenchida.
Como evitar
Guarde no cadastro do parceiro a UF de inscrição junto com a IE, para a consulta não sair na UF errada.