I thought that's how it is now. It's my understanding that there is a mutual agreement between providers not to tread into each others territory (I know it's true for the big providers at least).
Nope.
It's called franchising. Providers pay municipalities for exclusive rights to certain types of infrastructure. In the case of cable, there is no government law forcing them to lease the cable to competing providers either, as is the case with the twisted pair copper infrastructure.
What's hilariously, though, is that all this infrastructure was paid for by the tax payers anyway. Why it doesn't belong to them (through the local governments) is beyond me. Sure, AT&T has to lease copper to whoever asks for it (and jumps through the requisite legal, bureaucratic, and political hoops), but we still paid to put that shit in the ground in the first place.