"You can make searching his car be a condition of his parking on your driveway. He can always refuse and park elsewhere, of course."
If someone told me that I would leave, my car is my property. Period.
That's right. The employees though have economic concerns to deal with. That's why this back door gun grab by the companies involved takes the form of extortion. The companies both deamonize the gun owners and infringe on their rights, because the guns are used elsewhere, do not appear in the workplace and are kept private and unseen.
Other than very rare situations (such as a government installation), you're probably correct: the property owner can't force you to submit to a search, all they can do is deny you access to their property or kick you off their property.
However, if you consent to being searched as part of the conditions of employment, your employer can fire you for refusing to consent to a search. Generally speaking, your employer can demand that you consent to a search on the spot, even if no previous rule existed to that effect. If you refuse, he can fire you.