There is a reasonable argument for H-1Bs being the first to go, since the H-1B program was crafted to prevent noncitizens from displacing citizens in jobs, or driving down prevailing wages. The difficulty with this, of course, is that every employee is unique. A company can almost always justify the choice of one employee over another by pointing to differences in education, experience, or performance reviews. There are enough intangibles in that process to provide cover for whatever choice the company wants to make, even if it's driven by politically incorrect motives.
Gates did have a point, though; there is a shortage of home-grown talent in technical fields like engineering and computer science. Some NSF data may explain why American companies are reaching outside the country for their technical talent. In 1986, there were 58,736 undergraduate degrees in mathematics and computer science. Twenty years later in 2006, there were 58,588 math and CS degrees awarded. Math and CS represented 5.8% of all undergraduate degrees awarded in 1986, but only 4.0% of the 2006 total. In the same period, psychology rose from 4.1% to 6.0% of all undergraduate degrees awarded.
Although the number of graduate degrees in math and computer science has roughly doubled in the past 20 years, there's an important footnote: many of those degrees have been awarded to foreign students. To be specific, foreign students earned 63% of graduate engineering degrees and 35% of graduate science degrees. So, that increase in graduate degrees during the past 20 years has mainly gone to to noncitizens. As they graduate, they either return to their home country or get an H-1B visa and work for an American company.
The Bureau of Labor Statistics says the next decade will bring 37% growth in computer- and database-related jobs, which is much higher than most other occupations. If there has been no growth in American math and CS degrees over the past two decades, during a time when technology has become essential to our world, where will these workers come from? Microsoft could hire some of those abundant undergraduates with psychology degrees and train them on the job, but the company would prefer to hire people with formal CS training right out of college.
I don't see an easy way out of this mess, because we've gotten into it over a long period of time through innumerable bad decisions. We need improved public education, but also a new respect for science, engineering, and technology careers. Until our country can produce enough native-born graduates in these fields, we will need H-1B workers at least as much as they need us.