How does a company participate in this system? Are there headcount/turnover/etc requirements? What prevents someone from setting up companies that claim to employ anyone (you can "apply" for a nominal fee online and you get "hired" immediately and your chosen salary figure gets sent to these assholes)?

Most payroll companies support the integration. So step 1 is probably pay for an expensive payroll platform. They are going to have meta data for the fake company, so your $2MM salary is coming from a 1-10 person company with no website or anything might be suspect.

I think it’s difficult unless your company uses a big payroll processor like ADP or Paychex, who in turn report to TheWorkNumber. Faking payroll through one of those companies probably wouldn’t be worth the effort and you’d be setting yourself up for tax issues.

This is why I redirect the question to my comp requirements, instead of my pay history. Any company that absolutely insists on salary history is not one I will work for anyway.