Если никогда не светился в посольстве РФ в Оттаве что гражданин РФ, то можно просто получить визу в РФ.
Главное, заявить что не проживал ( не был прописан) в РСФСР на 06-02-1992г, хоть даже место рождения Россия.
Обсуждалось уже много раз. На вопрос: "состоял ли в гражданстве СССР или России ?" отвечать честно что:
"в гражданстве СССР состоял. Утратил в связи с исчезновением такого гос-ва в 1992 году"
http://forum.kamorka.com/viewtopic.php? ... 3&start=15
http://forum.kamorka.com/viewtopic.php?f=1&t=21248
Ну, если уж очень надо что и экстрим не страшен, то, можно рискнуть в анкете на визу написать что в Канаду прибыл как "лицо без гражданства."
Распечать вот это , как бы подтверждение, сего факта и послать вместе с документатми
на визу.
http://img38.imageshack.us/i/noticefrom ... canad.tif/
Также в сопроводительном письме на визу в РФ указать что документ с которым прибыл в Канаду из другой стрaны (тут уж возможны варианты: Прибалтика например) был сдан в passport canada, в обмен на канадский certificate of identity , ( вот дескать и подтверждение сего факта) , который в свою очередь, был обменян на канадский паспорт после получения гражданства Канады.
Еще можно обзвонить травел агентов по русским газетам: некоторые помогают с визами в РФ. Делают приглашение за ночь.