Напишу про свой свежий опыт, с вашего позволения:
Послала запрос (текст заявления в МИ ФНС Росси по ЦОД взяла частично из темы в этом форуме, частично из похожей темы в ЖЖ, плюс сканы обоих паспортов и листка убытия), распечатав/подписав/отсканировав, на nalog.ru 08.07.2015, тут же получила мейл о регистрации запроса.
14.07 - пришел мейл с nalog.ru о том, что мое заявление отправлено "по принадлежности" в МИ ФНС России.
Через две недели начала волноваться и позвонила в МИ ФНС по телефону +7(495)913-0760 Там автоответчик, надо дождаться чтобы соединили с оператором. Оператор сурово но вежливо спросила фамилию и сказала, что пакет документов сформирован и в течение недели будет отправлен по указанному в заявлении адресу (я указала адрес в Германии).
03.08.2015 мне пришел мейл из МИ ФНС о том, что справка отправлена заказным письмом. Там же был указан номер заказного письма, по которому его можно отслеживать на сайте почты России.
22.08.2015 письмо принесли. Правда, на сайте почты России статус у него до сих пор "ожидает отправки в Германию" :-)
Полезным оказалось то, что до того, как попросить справку, я зарегестрировалась на сайте госуслуг и по своему ИНН проверила наличие у меня задолженностей. Несмотря на то, что я 20 лет не живу в России, у меня оказалась задолженность в 27 рублей. Попросила родственников в Москве оплатить квитанцию и уже после этого заказала справку.