Companies have EINs (Employer Identification Numbers) that function like SSNs and are probably what they submit for that.

Correct. In theory I could get an EIN for my own company and use that instead, but that's more hoops than I'm willing to jump through and I'm not even 100% sure that would solve my problem, as they may tie it back to me another way.