Yes they can, if you worked for a job that hired you legally, paid you on the books, and reported your employment to the government for tax purposes. There are private investigation companies whose line of work is mining whatever information they can get their hands on regarding the names their clients give them, and putting together dossiers. As RedLeader said, you'd probably be horrified what one of these companies could turn up if you paid them and gave them your own name.
The thing is, hiring a private dick isn't cheap. You're really only looking at this amount of scrutiny if the employer is well off, and the job requires a high level of trust, responsibility, or security clearance, and there are quite a few well-qualified candidates vying for it. I would not tell the whitest of lies, either on the application or in the interview, if I was applying for such a position. I would just have a good (and succinct, and contrite) explanation ready, for any details about my past I wasn't proud of, if they happened to ask. Employers may or may not judge you for a spotty work history. But no employers have even the slightest tolerance for applicants or employees who've been dishonest with them -- many even make you sign a form agreeing to your immediate termination if they hire you, and then AT ANY TIME discover you lied during the application process.
So don't do anything on a high-trust job that would make the higher-ups look at you with suspicion, because that prompts background checks too. It's kind of like most places that drug test -- unless the place outright tells you that they randomly drug test everyone at regular intervals, then after an initial preemployment screen, chances are they'll only drug test you again if you injure yourself on the job (for insurance and Disability payment purposes), or someone suspects you're messed up at work.
Most employers who take your fingerprints and send them off to a private investigator are only going to get back your criminal record, maybe your driving record, and perhaps some information about what cities and towns you've lived in. There'll be nothing about who you worked for. The only way they verify that is by calling your references, typically.