In the US all one has to do is ask the FBI if they have anything about you. I did this in the 1970s to see if the Feds had anything on me for my anti-Vietnam War activities; they said no.
In the country where I'm currently eyeing and discussing a teaching job a police background check is required of every foreigner seeking to enter the country. A country has the inherent and absolute right to control its borders, so I haven't any problem with police background checks by governments or potential employers.
The problems occur when a government's classification and record keeping systems are poorly organized or organized without much care or attenton to accuracy and detail, as 7baht points out in his experience.
This background stuff still needs a lot of accurate sorting out by many governments, including in the West.