Este erro ocorre quando tenta consultar uma nota que não está registrada na base de dados da Sefaz.
Duas possibilidades seria você também tentar consultar a chave da nota no site da receita (http://www.nfe.fazenda.gov.br/portal/consultaRecaptcha.aspx?tipoConsulta=completa&tipoConteudo=XbSeqxE8pl8=), ou ainda fazer esta consulta no site da Sefaz do seu estado.
Vale dizer que em algumas situações excepcionais, por experiência própria já verificamos uma nota levar mais de 7 horas para ser reconhecida nas consultas e aparecer no site da Receita. Entretanto, vale dizer que é uma exceção, na maioria dos casos a nota deve aparecer em no máximo uns 10 ou 15 minutos.
Se por acaso está fazendo esta consulta com a intenção de retransmitir a nota, aguarde algumas horas e tente refazer a consulta. Se ela continuar retornando esta rejeição tente retransmitir uma vez, mas evite ficar retransmitindo para evitar a perda do xml posteriormente caso uma das primeiras tentativas seja aprovada.