One of the problems is that background checks are usually (in my understanding) done from private databases, not public records. When the OP says “removed from a criminal background check” it makes it seem as if this is a simple thing. I suspect that the conviction is still out there and whether it shows up in a background check depends on which source the hiring company uses.
The private databases are compiled from public records, so at some point they are updated to reflect what’s in the public records.
I would assume that a company that asserts you have a criminal record when the public record shows you do not - would be guilty of libel, and damages especially if their allegation causes you to be denied a job?
Possibly. But there is a general principle in (US) defamation law that a media source that accurately reports the contents of a public record is immune from suit. I don’t think there is necessarily a duty to update records on that basis; after all, a newspaper doesn’t have to destroy its archival materials that report an expunged conviction.
The same may not hold in other jurisdictions, of course.
Actually there are some states that have laws making this illegal.
Enforcing those laws is pretty much impossible. Unless an employer openly admitted to doing it how would one know he was discriminating because of an arrest record or just didn’t think the candidate was the right person for the job?
The same way you prove discrimination in any other case. Mostly, by introducing evidence that the employer’s hiring practices demonstrate a pattern.
But still, how is any particular applicant even going to know that? What pkbites says just two posts above is probably the most salient remark in this thread.
Somehow, applicants prove racial and other types of discrimination every day without advance knowledge of employers’ hiring practices. There are an almost infinite number of ways they might figure it out: reputation, a chance remark by someone working for the employer, a suit filed by another applicant, or the mere belief that they would have been hired if the employer wasn’t discriminating.
The difference is the laws regarding not hiring convicts are usually pretty open ended and allow for some discrimination depending on circumstances. For instance, if your crime was theft from your employer another employer isn’t going to get in trouble for not hiring you. The law allows for this type of discretion.
Also, people with criminal records tend to also have shitty work histories. Real easy for an employer to say you weren’t hired because your last company said you had an attendance problem. Your attendance problem being you couldn’t come to work because you were in jail is just a technicality. 
I didn’t realize that. How are the laws worded in the states you’re familiar with?
I know, but I’ve seen many job postings that state things like “Must be able to pass a drug screening and a criminal background check.”
I’m with you: what does “pass” a criminal background check mean? No felonies in 10 years? No felonies for life? No misdemeanors in 10 years? No misdemeanors for life? No arrests? No expungements? No traffic tickets?
… and is there a curve? 
Can’t speak for any of the cheeseless 49, but HERE is Wisconsin state statute 111.335:
**
111.335 Arrest or conviction record; exceptions and special cases.**
(1)
(a) Employment discrimination because of arrest record includes, but is not limited to, requesting an applicant, employee, member, licensee or any other individual, on an application form or otherwise, to supply information regarding any arrest record of the individual except a record of a pending charge, except that it is not employment discrimination to request such information when employment depends on the bondability of the individual under a standard fidelity bond or when an equivalent bond is required by state or federal law, administrative regulation or established business practice of the employer and the individual may not be bondable due to an arrest record.
(b) Notwithstanding s. 111.322, it is not employment discrimination because of arrest record to refuse to employ or license, or to suspend from employment or licensing, any individual who is subject to a pending criminal charge if the circumstances of the charge substantially relate to the circumstances of the particular job or licensed activity.
(c) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ or license, or to bar or terminate from employment or licensing, any individual who:
- Has been convicted of any felony, misdemeanor or other offense the circumstances of which substantially relate to the circumstances of the particular job or licensed activity; or
- Is not bondable under a standard fidelity bond or an equivalent bond where such bondability is required by state or federal law, administrative regulation or established business practice of the employer.
(cg) - Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to deny or refuse to renew a license or permit under s. 440.26 to a person who has been convicted of a felony and has not been pardoned for that felony.
- Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to revoke a license or permit under s. 440.26 (6) (b) if the person holding the license or permit has been convicted of a felony and has not been pardoned for that felony.
- Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ a person in a business licensed under s. 440.26 or as an employee specified in s. 440.26 (5) (b) if the person has been convicted of a felony and has not been pardoned for that felony.
(cm) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ as an installer of burglar alarms a person who has been convicted of a felony and has not been pardoned.
(cs) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to revoke, suspend or refuse to renew a license or permit under ch. 125 if the person holding or applying for the license or permit has been convicted of one or more of the following: - Manufacturing, distributing or delivering a controlled substance or controlled substance analog under s. 961.41 (1).
- Possessing, with intent to manufacture, distribute or deliver, a controlled substance or controlled substance analog under s. 961.41 (1m).
- Possessing, with intent to manufacture, distribute or deliver, or manufacturing, distributing or delivering a controlled substance or controlled substance analog under a federal law that is substantially similar to s. 961.41 (1) or (1m).
- Possessing, with intent to manufacture, distribute or deliver, or manufacturing, distributing or delivering a controlled substance or controlled substance analog under the law of another state that is substantially similar to s. 961.41 (1) or (1m).
- Possessing any of the materials listed in s. 961.65 with intent to manufacture methamphetamine under that section or under a federal law or a law of another state that is substantially similar to s. 961.65.
(cv) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ in a position in the classified service or in a position described in s. 230.08 (2) (k) a person who has been convicted under 50 USC, Appendix, section 462 for refusing to register with the selective service system and who has not been pardoned.
NOTE: Par. (cv) is amended eff. 7-1-15 by 2011 Wis. Act 32, as affected by 2013 Wis. Act 20, ss. 2365m and 9448, to read:
(cv) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ in a position in the classified service a person who has been convicted under 50 USC, Appendix, section 462 for refusing to register with the selective service system and who has not been pardoned.
(cx) Notwithstanding s. 111.322, it is not employment discrimination because of conviction record to refuse to employ or license, or to bar or terminate from employment or licensure, any individual who has been convicted of any offense under s. 38.50 (13) (c).
As you can see there are several times an employer can refuse to hire someone with a criminal record and it is not descrimination and sometimes when they cannot.
The twist is the statute says “and who has not been pardoned”. So that brings us back to the OP and whether it is discrimination to hold a pardoned crime against someone.