Thanks for your response. I didn't send my original passport, but our ZAGS did ask for a full copy of the passport (perhaps because they wanted to see the visa too, which is included in the copy). My girlfriend can do these processes you describe, but I didn't know it had to go through the same legalization through Russian foreign affairs and the Canadian Embassy. Would this take long, and would she have any problems mailing it? (I know sometimes customs are iffy about mailing marriage certificates)