Suena bastante a virus, aunque el tema de que lo hayas formateado es un punto en contra de esa idea.
No obstante, sigue este procedimiento:
1. Desconecta el PC físicamente de Internet.
2. Borra las particiones, rehazlas y formatéalas con el Gparted de Linux (descarga una ISO de Ubuntu y grábala, arranca con ella y borra particiones).
3. Escanea desde un PC que tengas 100% sano, TODO lo que le vayas a meter a tu PC (Windows, drivers, discos de software, etc).
4. Instala el software limpio.
5. Conecta el equipo físicamente a Internet.
Con eso estará descartado casi por completo que sea problema de virus que, aunque improbable con lo que dices del formateo, puede ser.
De otro modo, supongo que tu equipo está cogiendo los datos de la conexión mediante DHCP (automático, tú no configuras ninguna IP ni DNS ni gateway), ¿no?.