I wonder if municipalities are concerned with "suspicious" packages being placed on their domain? With everyone worrying about homeland security, drugs included, it may raise an eyebrow if people are "sneaking" around looking for suspicious packages?
The above is just a though for discussion.
But in reality, I can understand the concern that a municipality may have a problem with people disturbing natural areas with undue foot traffic. But in the same breath, and I've only been doing this for a VERY short time (2 caches), the folks interested in geocaching seem to be good folks out enjoying a wonderful hobby. The same folks I think are also very conscious, outdoor/environment loving people. That may be the majority, but I'm sure with just about anything, there are the minority who may not have the same intentions.
I haven't placed any geocaches yet, but I plan to. I don't think I'd place one without asking permission. But at the same time, you may need to educate them a little on what the hobby is about. If it IS in a sensitive area, you can always add that into the cache description.