loja em um Estado e Depósito em outro

Boa Tarde. Estou com um problema e preciso achar a solução. Como não sou contador, talvez seja uma dúvida primária pra vocês, mas pra mim está causando uma grande dor de cabeça.

Tenho uma loja em MG, onde é feita a venda (produtos sob encomenda, não são a pronta entrega) e o meu depósito (de onde sai o produto) fica em SP.

Como devo gera a nota fiscal neste caso? Eu gerava somente uma nota de venda no momento da saída da mercadoria. O problema é que o fisco está reclamando que a venda é feita em MG mas o ICMS está indo para SP. Como devo proceder?

Atualmente eu tenho o maior trabalhão porque gero uma nota de transferencia para a minha loja, que faz a entrada na nota e emite a nota fiscal de vendas. Isso faz com que o meu caminhão tenha que ir para a loja só para pegar as notas de venda.

Tem alguma solução melhor do que essa, onde eu possa emitir a nota diretamente do meu depósito para o meu cliente, sem ter que fazer a transferência para a loja e somente de lá emitir a nota de venda?

Obrigado a todos.

Bem Alessandro,

Vejo que o Fisco de lá está interessado e muito no seu ICMS. Não vejo problemas quanto ao seu procedimento anterior. Nunca vi isso, mas na minha opnião você deveria continuar procedendo da forma que o Fisco te orientou para não ter problemas, agora, seria viável você questionar o Fisco e tentar pegar a Base Legal em que eles alegam que você está errado em relação ao primeiro procedimento adotado por você anteriormente. Faça isso e poste aqui, para ver se conseguimos algo na Legislação de lá que possa nos dar uma luz.

Grato.