um_confused said:

Thanks everyone.. We've decided to consult with an immigration lawyer, as frege suggested. That would be next week. I will post lawyers suggestions. I am worried now, after I read your posts, NBanker.. but there is a question... how do people that live in Canada out of status for years do legalize by marrying canadian citizens? Even those, who entered illegaly, worked illegaly for decades?
Hi um_confused,
I presume that many of those people have been able to prove that they've established a genuine relationship and that they didn't enter into it for immigration purposes. The problem for them is the fact that it raises a suspicion in a visa officer's mind that the marriage may be one of convenience.
Also, misrepresentation to a border officer or to a visa officer is grounds for inadmissibility to Canada. So if they lied about what their intentions were when they first entered the country, they may have a problem.
If you read through sponsorship appeal decisions, you'll see that a good number of them concern failed refugee applicants who marry a Canadian. Sometimes their appeal is successful and sometimes it isn't.
Being in Canada illegally may not bar you from being sponsored, but the question in my view is how this will reflect on you in the visa officer's mind. I don't know if this is a serious enough concern to make it worth going back to the U.S. If I were you, this is something I'd ask the lawyer.
There is a question on one of the sponsorship forms: "Have you [...] ever been refused admission to, or ordered to leave, Canada or any other country?" So this kind of thing is at least a consideration for them.
As NBaker pointed out, there is also the potential problem of being ordered to leave Canada and having your in-Canada application terminated for that reason. How realistic a prospect this is is also something to ask.
In theory, you can leave Canada and attempt to re-enter legally as a visitor at a later time. In practice, being a U.S. citizen helps avoiding close scrutiny, and it is possible, but not certain, that there will be no questions about your previous overstay.