Removing regulations would do nothing to remove the immense cost to compete with the regional monopolies. In fact, in a completely unregulated economy that was unconcerned with anti-trust and monopolizing markets, I'm pretty sure that more of these mega ISPs would merge with one another. So instead of having four or five big ISPs nation wide, you'd have one or two.
The same convergence already happened in the phone industry, before they broke up Bell. Then Bell started to reassemble itself. In this particular space, the free market has been proven to move towards consolidation, for the benefit of big corporations and the detriment of their customers. Creating new competition seems to require government intervention.
So I guess you're pointing out that libertarians *think* they have a solution, but ignoring the fact that their solution has zero chance of working in the real world.