There are companies that exist solely to verify employment history, i.e., if you leave Company X, Company Y will confirm your time of employment, titles, etc. to new employer Company Z.
Most companies like that seem like they are just there to provide a plausible cover for legal liability. I've had multiple jobs that had background checks where I gave them my [1...n] addresses over the past 5-10 years and the background check comes back with me only have lived at [n-1] address with no indication that the data I supplied didn't match up with what they verified. If those companies we're doing their job they would at least tell my prospectvie employer, their client, that what they could prove didn't match up with what I said
"Doing their job" - they are data aggregators and brokers, if the data doesn't exist because it was never reported to a third party, there's nothing they can do.
If the whole point is to find discrepancies between what the prospective employee tells you and what is reality, not highlighting differences between those two sets of data is an issue, even if because the people doing the background check just lack access.
The real reason most background checks happen are so that companies have someone to point the finger at when one of their employees breaks the law. If that wasn't the case then you wouldn't get into situations like background check companies reporting completely clear records when the government has a simple process to show you every sentence given to someone. They stick to third party companies because they are cheaper and don't trigger compliance regulations required by law.
They would go for the better, if slightly more expensive, data source in a heart beat if finding about criminal history was the actual goal
