Отказ ГИБДД в этой ситуации неправомерен - обязанность по уплате штрафа считается исполненной с момента внесения денег, а не с момента отражения оплаты в базе ГИБДД (ст. 32.2 КоАП РФ). База ГИС ГМП - это техническая система, сбои и утеря данных там не редкость, особенно за такой давний период, и сама по себе она не является правоустанавливающим документом.
Но есть серьёзный практический нюанс. С момента лишения прошло почти 10 лет. Во-первых, у банка может уже не сохраниться архив платежа - обычные сроки хранения операций 5 лет, дальше нужен отдельный запрос с обоснованием. Во-вторых, если водитель не пришёл за удостоверением в течение 3 лет после истечения срока лишения, оно по правилам считается невостребованным и подлежит уничтожению - тогда ГИБДД физически нечего Вам отдавать, и вопрос уже не в штрафах, а в том, что придётся получать удостоверение заново через пересдачу теории и медсправку. Это надо прояснить сразу, чтобы не тратить время зря.
Ещё момент: если по одному из постановлений истёк двухлетний срок предъявления к исполнению (ст. 31.9 КоАП РФ), взыскание по нему вообще становится невозможным - это дополнительный аргумент в Вашу пользу, если окажется, что оплату всё же не смогут подтвердить.