I've worked for a bunch of companies (i'm a us citizen), and I've never had this problem. These days it actually seems like companies ONLY want to hire Citizens or GC holders. Pretty much everywhere i applied to when i wanted to change jobs this year asked if i was a Citizen/GC Holder. I know a h1b guy whose company got bought out and they fired all the H1B's, the guy sent out like 300 resumes before finally getting 1 interview and he told me it will take him 20/30 years to get his GreenCard. From what i know about him, life as a H1B is essentially a slavish like existence.