Roberta X had a post on gun rights vs. property rights that finally helped me figure out how to justify my gut feelings.
I believe in both property rights and gun rights. My gut feeling was that in general, businesses shouldn't be allowed to ban guns from their parking lots, but I couldn't justify it with my views on property rights.
After reading Roberta's post, there are several things that are important and provide support for my gut.
First and most important is that corporations are not people, and the limitations on corporate liability come at a price of limiting corporate rights.
Second is that areas open to the public are different than private areas of a business, even if corporate owned. This includes to a lesser degree employee lots without access controls.
Finally, you retain property rights to your car, even when it is on someone else's property.
This boils down to a corporate owned public parking lot having virtually no rights to either ban guns or to search your car for them. A privately owned lot has a bit more rights, but they still can't search your car unless you have explicitly agreed--A sign saying "subject to search" is not an explicit agreement.
I think guns in corporate owned public areas not in a car are somewhat protected, but there are limited circumstances where they can be banned--bars and gun shows should be able (but not required) to ban carry. This needs to be with explicit assumption of liability, and at least some steps to minimize risk.
Corporate owned private areas, and individually owned public areas are where I think the balance tips toward the property owner. A corporation may ban guns from 'areas not open to the public without specific invitation'. Even here there are some areas where rights go the other way--They cannot restrict a trucker from having a gun locked in his truck (unless they provide storage) even if others in the area are restricted.