Causa:

Quando for emitida uma NF-e com Operação de Destino (Campo: ide / idDest) igual à "3 - Exterior", com UF do destinatário igual à "EX" - Exterior e o Código do Município (Campo: dest / enderDest / cMun) 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".


Campos no XML:

<ide>
...
    <idDest>3</idDest>
    <cMunFG>4314902</cMunFG>
    <tpImp>1</tpImp>
    <tpEmis>1</tpEmis>
    <tpAmb>2</tpAmb>
    <finNFe>1</finNFe>
    <indFinal>1</indFinal>
    <indPres>1</indPres>
    <procEmi>0</procEmi>
    <verProc>zx</verProc>
</ide>
...
<dest>
    <idEstrangeiro/>
    <xNome>NF-E EMITIDA EM AMBIENTE DE HOMOLOGACAO - SEM VALOR FISCAL</xNome>
    <enderDest>
        <xLgr>AVENIDA SAN MARTIN</xLgr>
        <nro>148</nro>
        <xBairro>EQUIPETROL</xBairro>
        <cMun>4314902</cMun>
        <xMun>EXTERIOR</xMun>
        <UF>EX</UF>
        <CEP>00000000</CEP>
        <cPais>0973</cPais>
        <xPais>BOLIVIA</xPais>
    </enderDest>
    <indIEDest>9</indIEDest>
</dest>


Solução:

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.