Boa noite!
Pelo que entendo, para resolver esse impasse e manter a legalidade da operação, você tem duas alternativas principais: emitir em operação triangular (remessa por conta e ordem) ou abrir uma filial em São Paulo.
Atualmente, não é permitido simplesmente alterar o endereço do remetente sem um vínculo fiscal registrado, pois isso é classificado como fraude ou sonegação pela Receita Federal.
Espero ter ajudado.