" Remember two things:
1. Your workplace, including the parking lot, is private property and the owner of said property makes the rules. "
If the store is in a shopping mall / strip mall where parking is accessible to all, I doubt a specific store can make the rules for everyone. If having a gun in a common parking lot is legal for customers, it is legal for everyone since the store really does not own / or specifically rent the lot.
There are state / federal laws and there are company generated " laws " . The " company laws " may or may not have any real world enforceability.
If the OP parked across the street, could the store still search their car? Doubt it. How about if he took a taxi or bus, would the bus be subject to search after he got on it? ( yes I know he would not be leaving a gun in the bus when coming to work. )
And just who would be performing this search? Can the employer trash the car in the process of the search? ( Like a border check point where they literally tear the car apart if drugs are suspected. ) What if the employee didn't have the key to a glove box, truck cap or interior mounted lock box , would the store tear the car apart? Say the store calls the police,could the police do a warrantless search?