The way the MIT team managed "fraud" was that a picture was required. This isn't like a spot the terrorist problem either though - but perhaps it also provides insight into how to improve the effectiveness of rewards.
It's not like a terrorist is like a red balloon at clearly visible intersections (as per the contest design in this case). But maybe rewards should be designed such that they also incentivize the second order referral network to encourage more people to care (in effect creating something of a decentralized team) - perhaps encouraging a referral network to train others to the task.
There are all sorts of problems though if the target is a terrorist though. Recently the bigger problem seems to be home grown terrorists so it's not as if they'd stick out. If the problem is applied to a place like Afghanistan in hunting for insurgents, there could well be a number of disincentives to the local population to reporting it (whether it be out of loyalty or fear) and those disincentives might considerably greater than the incentives - particularly to the referral network - a network I'd add would know your loyalties in a rather dangerous place. Similar problems for finding a bomb or anything that doesn't want to be found for that matter.
Maybe there will be a future challenge where the balloons are more hidden. It also reminds me of this: http://news.ycombinator.com/item?id=955793