Somente para registro, aqui na região de Cabo Frio/RJ atendida pela Oi Velox, houve essa instabilidade de conectar alguns sites de forma aleatória. Como é uma Lan House com vários computadores foi notado que variava bastante de site para site e de computador para computador.
O comportamento me levou a pensar em algum problema de servidor DNS, procedi testes e usei outras opções. A conexão voltou ao normal após um tempo, de mais ou menos uma hora, mas não pude precisar o momento exato que começou a acontecer pois o estabelecimento abre somente as 11 horas.
Apesar disso, tive a impressão que nada que fiz foi a razão de ter voltado ao normal.