Если(!) верить страницам консульств, то справка нужна (в том или ином виде, см. ниже).
На "франкфуртской" странице написано следующее:
"Представление документа об отсутствии задолженности по уплате налогов требуется от всех российских граждан, проживающих на территории иностранных государств и обратившихся по вопросу о выходе из гражданства Российской Федерации." http://www.ruskonsulatfrankfurt.de/Rus/vyhod-4.htm
На "боннской" странице есть еще и такая информация:
"По Вашему желанию Генеральное консульство может самостоятельно истребовать информацию об отсутствии у Вас задолженности по уплате налогов. В этом случае вместо указанной справки представляется: Свидетельство о постановке на учет в налоговом органе физического лица по месту жительства на территории Российской Федерации (при его наличии) и его ксерокопия, либо сведения об Идентификационном номере налогоплательщика (ИНН) (в случае если он присваивался). При отсутствии сведений о присвоенном ИНН, его можно проверить через интернет-сайт ФНС России (https://service.nalog.ru/innmy.do). Такая проверка возможна только при наличии внутреннего паспорта гражданина Российской Федерации или паспорта гражданина СССР образца 1974 г." http://www.ruskonsulatbonn.de/ru/consinfo/citizenship/ig-13.php
Это вроде вы хорошая новость, но нужные бумажки есть, наверно, не у всех...