Você poderá emitir as novas notas com o novo endereço daqui para frente, mas as notas antigas devem permanecer com o mesmo endereço, afinal, o serviço foi prestado naquele lugar.
Muitos municípios possuem no próprio sistema estas informações, de modo que elas não são informadas no envio das notas. Neste caso deverá acessar o sistema online do município com seu cnpj e senha e atualizar lá.