ARC and work permit aren't the same. If you are working, you need to ask your boss to produce the work permit. If he doesn't, I would run, not walk away from that place. The work permit is required to apply for the ARC. The former allows you to legally work, the latter to legally reside (in this case based upon your job).
I agree with others, your boss sounds a bit suspect and determining your work permit status is likely far more important than any background check issues you may or may not have.