Olá Alexandre,
Aqui estava com um problema semelhente, a unica que chega efetivamente é a Telefonica... mas obtendo informações verifiquei que operadoras de outro estado podem atuar em qualquer região fornecendo serviços... tente com a GVT que tem preços competitivos, Neovia, Impsat, Brasil Telecom, na sua região não sei quem fornece energia elétrica, mas entre em contato pois quase todas as fornecedoras de energia elétrica agora fornecem link dedicado tal como a Eletropaulo e CPFL (área Telecom).
Boa sorte
Anderson