Emissão de NFS-e para empresa estrangeira COM CNPJ

Prezados,

Estou com dificuldades para emitir NF de um serviço prestado no RJ para uma empresa estrangeira, que tem CNPJ. No sistema NFS-E, ao inserir o CNPJ da empresa, surge a mensagem "A inscrição informada não foi encontrada no cadastro de CPF/CNPJ". Conferi no sistema de situação cadastral da Receita e a empresa está ativa. 

O serviço já foi pago, em Reais, de uma conta em banco no Brasil para uma conta em banco no Brasil.

Ressalto que a empresa foi inscrita no CNPJ em Abril.

Alguma luz? 

Boa Noite,

Eu acho que o problema está no cadastro da prefeitura, se o endereço estiver como EXTERIOR, o campo CNPJ deverá seguir em branco.

Confira o cadastro na prefeitura, acho que esse é o caminho.