Так вот в итоге после всех звонков в амты и разговоров со знакомыми, выясняется, что у всех кто приехал раньше, например в 90-ые есть Einbürgerungsurkunde

Не у всех.

Только у тех, кто после получения 4 и 7 параграфов подал АНТРАГ на получение гражданства Германии.

А те, кто подобного антрага не ставил, примерно в октябре 1999 года получили Staatsangehörigkeitsausweis. В котором сообщалось, что 1.08.1999 года они приобрели немецкое гражданство

und Vertriebenenausweis.

Вы уверены?

Der Vertriebenenausweis nach § 15 Bundesvertriebenengesetz (BVFG) in der bis zum 1. Januar 1993 geltenden Fassung dient zum Nachweis des in § 1 BVFG festgelegten Vertriebenenstatus. Er musste bis zum 31. Dezember 1993 beantragt werden. Zuständig für die Ausstellung sind die Länder. Diese sind an die Feststellungen zum Vertriebenenstatus im Aufnahme- und Verteilverfahren nicht gebunden.
Ab dem 1. Januar 1994 wird die Vertriebeneneigenschaft nur noch auf Antrag einer Behörde festgestellt (§ 100 Abs. 2 BVFG).
Spätaussiedler, d. h. Personen mit deutscher Volkszugehörigkeit, die die Aussiedlungsgebiete nach dem 31. Dezember 1992 verlassen haben, erhalten zum Nachweis ihres Status eine Bescheinigung nach § 15 Abs. 1 BVFG, ihre in den Aufnahmebescheid einbezogenen Ehegatten oder Abkömmlinge eine Bescheinigung nach § 15 Abs. 2 BVFG. Mit Ausstellung dieser Bescheinigung erwerben sie (seit dem 1. August 1999) kraft Gesetzes die deutsche Staatsangehörigkeit nach § 7 Staatsangehörigkeitsgesetz.