Causa
Quando for emitida uma NF-e com Operação de Destino igual à "3 - Exterior", com UF do destinatário igual à "EX" - Exterior e o Código do Município diferente de "9999999", será retornado a rejeição "509 - Informado código de município diferente de “9999999” para operação com o exterior".
Exemplo:
Foi emitida uma NF-e com Operação de Destino para o Exterior, UF igual à EX e Código do Município igual à "4314902".
Como Resolver
Deve-se informar o Código do Município igual à "9999999" nos dados do Endereço do Destinatário quando a Operação descrita na NF-e for com o Exterior.
Corrigido o Código do Município no Endereço do Destinatário, basta reenviar a NF-e para processamento.
Referência
Manual de Orientação ao Contribuinte - http://www.nfe.fazenda.gov.br/portal/exibirArquivo.aspx?conteudo=9hd38oni4Nc=
Nota Técnica 2012/004 - http://www.nfe.fazenda.gov.br/portal/exibirArquivo.aspx?conteudo=FbhXv6LN5zw=