Natural gas is deregulated in some places: http://www.ohionaturalgas.com/deregulation.html

Honestly though, large utilities are a good case of a "natural monopoly".