Uncle Buck, some companies might be better off with mimes working their CS lines...
But I digress.
In answer to your question, I am pretty sure both TX and FL passed laws denying employers the right to ban guns in parking lots. Florida provided some exemptions for security-sensitive businesses (munitions storage facilities are a specific example that spring to mind, as Disney was trying to use the fact that they have fireworks as a way to work the loophole); I think Texas has similar language about businesses with security perimeters, but I'm not sure.
And I think you're right about letter writing being more readily available than tort reform. Based on my experience (and the experiences of others) with IKEA, though, I don't have much faith in their effectiveness, unless a MAJOR grassroots campaign takes place.