They shouldn't call it a "random" search.

The US INS requires visa for passport holders of all countries with about a dozen or two exceptions. They based the exceptions on the percentage of illegal aliens. People from countries like Switzerland don't need to come to the US to pick strawberries.

On a similar note, selected searching is much more effective. Criteria could change as the terrorist profile changes.

Let's look at the math, oversimplifying and increasing the %. Say 1% of the public is dangerous, but 5% of the men from a certain country are terrorists. Say there are 10,000 ordinary people and 100 from the high risk group. Search 100 passengers and you are likely to miss all 5 of the high risk terrorist (5% of 100). Search 80 of the passengers and 20 of the high risk group and you may catch 1 of the 5 terrorists.