In my city it's common for large retailers to provide parking lots at a cost. If you buy something, the cashier gives you a stamp that nulls your parking charge. Anyone can park, but free for customers. There's ways to game it, but it seems a workable solution.
I've only seen parking validation for private garages. Are your parking spaces owned by the city, and retailers can still validate for downtown, on-street parking?
