Yes they do. I just got a h1b job. This is my blog post on that - http://sans-voir.livejournal.com/9189.html.
In fact I tried your option 2 (get a job at big co and ask relocation), though that was in Canada, but got rejection after onsite interviews.
You relieved my feelings -- most of my friends say it's absurd not to go through the usual university path.