Even if there is no cable company (and they aren't paid off), there generally is a franchise fee for the honor of providing service to county, city or town, and Verizon would need permission of the local government (and payment of the franchise fee, which is often both a lump sump and a fee per month per subscriber) to bring FiOS to the area. DSL is already covered by the Telephone franchise Verizon has.
Suffices to say that in many area, the local cable company fights tooth and nail (hires lobbyists to convince the local government that competition and improved service for customers is a bad idea). There is a reason cable industry has such a bad reputation....