Then as a Canadian don't you have tax records? I'm sure that is proof of residence. All of these other exchanges you have to verify with as well, so your not going to get around the fact that you need some kind of evidence. Gox or not.
+
and bitstamp is much more safe. BTC-e is ok when it works, but the support is extreme sillent (1 sentence per day).