Вообще эта справка - не Ваша проблема, а проблема того подразделения ГАИ, которое будет принимать у Вас экзамен и выдавать ВУ. Они должны будут самостоятельно сделать все запросы по этой теме. Существуют вполне себе однозначные "ПРАВИЛА СДАЧИ КВАЛИФИКАЦИОННЫХ ЭКЗАМЕНОВ И ВЫДАЧИ ВОДИТЕЛЬСКИХ УДОСТОВЕРЕНИЙ", в которых четко написано:
10. К сдаче экзаменов допускаются лица:
1) прошедшие медицинское освидетельствование и имеющие медицинскую справку установленного образца о годности к управлению транспортными средствами соответствующих категорий (далее именуется - медицинская справка);
2) прошедшие подготовку или переподготовку на получение права на управление транспортными средствами соответствующих категорий и получившие документ о прохождении подготовки (переподготовки) в образовательных учреждениях независимо от их организационно-правовой формы и подчиненности, имеющих лицензию на осуществление образовательной деятельности (далее именуется - образовательное учреждение).
Подготовка водителей на получение права на управление транспортными средствами категорий "А" и "В" может также осуществляться в индивидуальном порядке путем прохождения подготовки в объеме соответствующих программ у специалистов, прошедших аттестацию и имеющих соответствующую лицензию, или самостоятельно.
Подготовка водителей транспортных средств осуществляется на основе примерных программ подготовки водителей транспортных средств различных категорий, утвержденных Министерством образования и науки Российской Федерации по согласованию с Министерством транспорта Российской Федерации и федеральным органом управления Государственной инспекции;
(в ред. Постановления Правительства РФ от 14.02.2009 N 106)
3) достигшие возраста:
шестнадцать лет - для категории "А";
восемнадцать лет - для категорий "В" и "С";
двадцать лет - для категории "D", а также для управления трамваями и троллейбусами;
....
и
16. Лицо, желающее получить право на управление транспортными средствами соответствующих категорий (далее именуется - кандидат в водители), представляет в Государственную инспекцию:
1) заявление;
2) паспорт или иной документ, удостоверяющий личность;
3) документ, подтверждающий регистрацию кандидата в водители по месту жительства или по месту пребывания (при наличии регистрации);
4) медицинскую справку;
5) документ о прохождении обучения (за исключением лиц, получивших подготовку в индивидуальном порядке);
6) водительское удостоверение (если ранее выдавалось);
7) фотографию (за исключением случаев автоматизированного изготовления водительских удостоверений в Государственной инспекции);
8) квитанцию (платежное поручение) об оплате сдачи экзаменов.
Ни о какой справке о том, что ранее ВУ не выдавалось, упоминаний нет. Соответственно и предоставлять ее Вы не должны. Из чего однозначно вытекает, что и требовать таковую у Вас не имеют права.