Depending on the specific facts in the application they make, they should in principle be eligible for a work permit. If a person is in Canada under a stay of deportation, according to the regulations they are eligible to receive a work permit. The officers are required to make that assessment objectively. They can't do so prejudicially and say, “I don't like this character. He seems a bit dodgy or unpopular. I'm therefore going to use my personal discretion, against the regulations, to deny him a work visa.” That's simply not allowed.
On February 10th, 2009. See this statement in context.