In many states, criminal background checks by local law enforcement agencies only reveal convictions in that particular state and not other states. These checks also generally require exact matches of name and date of birth so a minor inconsistency (either deliberate or accidental) can result in a "no match" return.
There are many, many private service providers that offer criminal background checks. These range from online services costing only a few dollars to complete background investigations costing thousands of dollars.
I have a short article on this topic on my website Security Background Checks This is written primarily for the end-user but may also be of interest to integrators and contractors.
I think that any service provider in the security/surveillance industry should conduct preemployment background checks on all employees, particularly those being sent out in the field or working in other positions of trust. Not conducting checks can place your company in a position of liability and can result in some very damaging publicity should one of your employees commit a crime while working at a customer's site.