Как избежать повторной оплаты транспортного налога, если авто на учете в другом регионе?

Здравствуйте, Артём. 

Так как Вы сменили место жительства, а автомобиль на Вас зарегистрирован, то считается что он уже не находится по первоначальному адресу регистрации. 

НК РФ Статья 363. Порядок и сроки уплаты налога и авансовых платежей по налогу

 
1. Уплата налога и авансовых платежей по налогу производится налогоплательщиками в бюджет по месту нахождения транспортных средств.

Учитывая, что Вам слали по ошибке налоговые уведомления из другого субъекта, стоит обратиться в ИНФС, которой Вы оплачивали налог с письменным обращением относительно ошибочно уплаченного налога по вине ИФНС. А по новому месту жительству нужно будет налог уплатить.