How about: an insurance policy such that, if the employee does end up stealing, then the employer is made whole. The former-thief employee could pay for such a policy, and then it would seem the employer would be indifferent between the former thief and the average applicant. The policy could be paid for out of the thief's salary; he would effectively be accepting a lower wage.

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.