I provided my employment agreement to the new company when they asked for it.
Probably put his previous job on his resume or they looked up his previous job using a credit reporting bureau
Often it's just that the two companies are aware of each other's policies. If they've heard of Company B and know it has a non-compete they just reject you.
Kind of weakens the argument for negotiating the non-compete clause(s) out of the contract. You might get screwed anyway if the hiring company assumes you had to sign one.