Весь вопрос в том,на каком основании они получали новые паспорта.
Ст3 Положения о паспортной системе СССР от 28.08.1974 года прямо указывает что,цитата-"Запись о национальности в паспорте производится соответственно национальности родителей. Если родители принадлежат к разным национальностям, то при выдаче впервые паспорта национальность записывается по национальности отца или матери в зависимости от желания получателя паспорта. В дальнейшем запись о национальности изменению не подлежит"
Данная статья не правилась,ее действие не отменялось и изменения в нее не вносились вплоть до 1997 года,т.е до принятия нового положения


Я не сомневаюсь в том что находились люди которые все же каким то путем меняли национальность,даже предполагаю некоторую географическую зависимость таких случаев( как правило Казахстан и другие новые страны Средней Азии).
И более того,лично знаю человека провернувшего такой трюк в Кокчетаве,но и немцы оказались совсем не дураки и прекрасно знали что изменение национальности в паспорте не могло быть законным и естественно завернули трюкача на стадии рассмотрения.
Так что вопрос не в том что такое было возможно а этом насколько это было законно и как немцы относились к таким заявителям

очевидно немцы относились к этому, как к вполне законному (что не мешало им, разумеется, таким заявителям отказывать):

Es gibt keinen konkreten Hinweis auf einen der Klägerin bereits im Jahr 1991 ausgestellten Inlandspass; seine Existenz lässt sich allenfalls deshalb vermuten, weil die Klägerin im Oktober 1991 16 Jahre alt wurde und nach dem damals noch geltenden sowjetischen Passrecht einen Inlandspass benötigte. Die Klägerin hat in der mündlichen Verhandlung vor dem Senat plausibel erklärt, warum sie trotz behördlicher Aufforderung im Jahr 1991 keinen Inlandspass beantragt hat. Damals betrieb ihre Mutter O. C. eine Änderung ihres bislang russischen Nationalitätseintrags und erhielt am 24. Juli 1992 einen neuen Inlandspass mit deutschem Nationalitätseintrag.
https://www.justiz.nrw.de/nrwe/ovgs/ovg_nrw/j2016/11_A_802...

из этого следует, что смена национальности была возможна даже до вступления в силу Конституции РФ (вероятно на основании прямого действия "декларации прав и свобод человека и гражданина", принятой ВС РСФСР 22.11.1991).