Most employers outsource payroll and those payroll companies sell the data. You can get the employment record of most applicants this way.

HR actually calls/emails to verify employment dates/eligible for rehire, though I wouldn't be surprised if some of it was automated (like the other poster noted) through payroll data to catch the omitted company B.

For most companies they'll just find them directly and call, and if they can't for whatever reason (company doesn't exist anymore, multiple companies with the same name) they'll ask the candidate to provide a point of contact.

Of course now that I said that out loud I suppose the next step for a candidate is to provide a fake number/email as a reference, but that doesn't really work if you say that you worked at Amazon/etc.