Acho que o problema da falta de link do provedor, é um problema do provedor e não dos seus clientes. Nesse caso, os clientes nem precisam pensar 2x em trocar de provedor. Acho que isso acontece em poucos casos, pois quando começa a querer saturar o link, o empresário tem q estar atento pra já contratar mais link. Salvo ocasiões em que ficamos refém de uma única operadora.
Dêem um traceroute (ou tracert no windows) e vejam a quantidade de rotas até chegar no simet.nic.br. Não tem como garantir a velocidade até lá.
Acho que o lance para podermos ter uma base, é testar a velocidade em 2 ou mais medidores. Eu sempre usei Copel e Speedtest.