What will satisfy you then? Should people who come out from prison for stealing sit around jobless since nobody trusts them? That's bound to get them back into prison.
There was an article a little while back about a company tracking the employees behavior on the computer, and a lot of people mentioned that ‘if you are not trusted regardless, what incentive do you have to be trustworthy’.
This is the exact same thing.
If the job is minimum wage, of course, then it's not possible to lower the wage further.
Also, discovering the theft and proving it was that employee might be difficult.