Here in Canada only certified service dogs are allowed in food stores, restaurants etc., and never unleashed. Where are you geographically, generally I mean? Maybe a lot of people in your jurisdiction need to get of the couch and deal with the issue. Here it's a public health matter, simple as that.

What you describe in shelters sounds like a bad movie, but when legislators make it so, that's what you get. Does your area have fewer people voting and fewer people politically active between elections? Anyway with such a great increase in allergies in the last couple of decades, if your scenario is correct it seems more than a little dumb to add medical (i.e. asthma) emergencies to a disaster by not segregating critters.