I think the work history requirements might have relaxed in recent years a bit, but not by much. 10 years seems to be the point where most American employers start to seem optimistic about being able to get you an H-1B without a degree. But if it's not employment experience you'll have to work twice as hard to document it, and that can be very difficult. Most of my work history, for example, is tied up in companies that no longer exist or as contracts, as with you.
http://careers.microsoft.com/careers/en/ca/home.aspx https://jobs.ea.com/locations/canada/ http://www.google.ca/about/jobs/locations/waterloo/
I also think there was an article here recently about Facebook setting up a Vancouver office just to bring graduates through the subsidiary employment process. It's a one year thing specifically for that purpose.
I really did mean a four-year; I just said "diploma" because "degree" implies education was involved. The diploma is the piece of paper. :)
> prove work history for 3 or 4 years
Does that mean employment history? I don't have much of that. Completed contracts, certainly, but I've not been "on payroll" anywhere for more than six months at a time.