I concur. I work for a city, managing the Public Safety radio system. I see the same thing in our city. They do not want towers, but everyone complains about coverage.
Talk to Verizon. It may be also that you are on the edge of their footprint and they have to be sure they do not encroach on the neighboring carrier's area. That is a big issue here in North Carolina because Verizon is only licensed for some areas, not the entire state.
Rik