А можно немного уточнить вот этот момент:
> Дело в том, что так уж сложилось, что я родился в СССР. После его развала я потерял гражданство и остался лицом без гражданства
Как так могло произойти? Я тоже родился в СССР, и после развала ходил некоторое время с паспортом СССР. А потом его просто поменяли (был массовый обмен паспортов). Никаких проблем с этим ни у кого из знакомых не было.
Может быть тут было какое-то нарушение закона, и паспорт вам должны были выдать, и стоит копать в этом направлении?