Ой, какая сложная ситуация, бывая в консульстве слышала истории людей оказавшихся без гражданства - волосы дыбом встают. Мой вам совет, как идея: если подтверждение наличия не прошло, то:

1. попытаться подтвердить повторно, но на основании других документов: если регистрационных архивных доков не находят в россии, какие есть у вас на руках из России? Аттестат со школы, диплом, заключение о службе в армии, заключение брака, подтверждающие проживание там? Неужели даже свидетельства о рождении нет? Уж на месте Рождения должны быть архивные данные, позволяющие вам запросить копию, не мог Загс все просрать. Как вы когда-то получили ВНЖ, для него же всегда нужно было свидетельства о рождении?

2. попытаться вступить в гражданство заново на основании родителей с росс.гражданством (но нужно свидетельство о рождении, доки родителей типо справка о браке и тд).

п.с. совет всем людям, никогда не ждите, пока просрочится пасспорт, делайте новый вовремя (через консульство например), потом оооочень много головной боли, как можно этого не бояться, особенно, если у вас второго гражданства "на всякий случай" нет...