Sorry man, that is horrible. I work as a Civil Engineer and deal with zoning, permits, etc. all day long. Every city is different, but I've run into similar situations with parking requirements. We just changed our ordinances to allow shared parking (which does what it says). This works especially well if two business have different operating hours (movie theater and dentist office for example.) I'm sure you've looked at every option, but I just thought I'd mention it.
It really bothers me when municipalities negate common sense for regulation (like not counting the parking structure you are next too). Anyway, I thought I'd send you my condolences.