Ну, ИНН не у всех и есть. Если я правильно помню, ИНН физическим лицам начали присваивать где-то в самом конце 90-х годов, чуть ли не в 1999г. Некоторые выехали сюда раньше, так что ИНН не получали.
А у Вас справка какая, вот такая? http://www.klaipeda.mid.ru/doc/obr_z.jpg
В принципе, если справка выдана уже после оформления приказа, то Вы всё сделали правильно - справку запросили, её Вам выдали. Но консульство, как Вы правильно заметили, - специфическое такое место. Могут послать куда подальше. А могут и принять всё, как есть. Кстати, в этом случае, как видим, тоже нет гарантии, что через полгода не скажут, что справка не та, надо переделывать...
(Моя знакомая только что запросила такую справку в МИ ФНС по ЦОД. Посмотрим, что ей пришлют.)
P.S. Учитывая ответ Lana_21, начинаю думать, что tom4ik-то, может статься, отчасти и права: хоть речь идет и не о справках из домуправления, но все-таки и не о налоговых справках, а о форме бланка заявления на выход из гражданства. Это намного проще, чем новую налоговую справку запрашивать.