Ситуация действительно неприятная.
и п.2ст.126 действительно третьих лиц касается.
Попробуйте обжаловать в управление, надеюсь у вас есть договор аренды с актом на новый адрес + решение о смене адреса прошло, данные в реестрах о новом адресе должны быть, с учета вас сняли. Вам нужно подтвердить, что вы реально не получали никаких запросов. Неплохо было бы взглянуть кто там расписался им в уведомлении о вручении

И заверить налоговые всех инстанций в готовности предоставить подтверждающие документы по первому требованию.
Хотя лично я сторонник решения конфликтов в горизонтальной плоскости. Сходите на прием к начальнику отдела, к начальнику налоговой с документами о том, что вас там не было, сняты с учета, стоите на учете в другой налоговой и договором аренды (или что там у вас на новый адрес), подтверждающим ваше фактическое нахождение не там, куда они запросы посылали.