A naive analysis with a high cost of not finding malfeasors would say that we should sample all people whose probability is above some threshold. (This threshold depends on available resources.)
However a more sophisticated analysis takes into account the possibility of a terrorist dry run to figure out who will be detected, and who not. Then the terrorists can launch their attack knowing that they will not be detected.
There may be fewer available terrorists who register as low probability p, but they can find enough for their attack. For a real life example, screening went up for people from the Middle-East after 9/11. So Al-Qaeda found a London born mulatto named Richard Reid for their next airplane bombing attempt. He didn't fit the profile, sailed right through screening, and only luck and an observant stewardess saved the airplane from the bomb in his shoe.
If you assume that the terrorists have sufficient candidates available, and are aware of the screening protocol, you should assume that they will always use the candidate that they have that is least likely to be caught. Therefore the most efficient use of resources would be to randomly screen everyone with the exact same probability.
If you don't assume that terrorists have unlimited potential candidates, then some profiling is worthwhile. But not that much - the enemy should be assumed to be relying on their most difficult to spot members, so the obvious criteria are not going to be nearly as predictive as you would hope.