Отказ в визе в Россию бывшим гражданам России.

Уж сколько раз твердили миру... (с) Мда.
Сколько лет уже пишут на форуме, что ни в коем случае не надо отдавать оригинал справки, но нет, все равно кто-то отдает. И даже копию для себя не сделали. Это Вы, конечно, совсем не подумали.
Мне приходят в голову 2 возможных способа получения визы:
1) Пройти проверку наличия гражданства РФ. Минусы: дорого и долго. Плюс: получите официальную бумагу (которую не надо никому отдавать!), что гражданства у Вас нет. В Вашей ситуации этим стоит заняться в любом случае.
2) Найти на просторах Германии "русскую" турфирму, где в список документов справка о выходе из гражданства пока не входит. Такие фирмы до сих пор есть, может быть, Вам кто-нибудь здесь подскажет контактные данные. Плюсы: так намного быстрее, чем проходить проверку на наличие гражданства. Минус: даже если Вы сейчас обойдете это требование, бумага об отсутствии гражданства может потребоваться в следующий раз, поэтому лучше озаботиться ее получением.