En mi caso, casi desde cualquiera de los países de Europa, las peticiones a Github se enrutan al datacenter de Frankfurt, y es ahí donde el proveedor que usa Movistar va realmente mal. (twelve99)
La solución temporal para no tener que estar en la VPN todo el tiempo es enrutar el tráfico de GitHub al datacenter de UK, usando una IP fija en /etc/hosts.
20.26.156.215 github.com
Para encontrar las IP en rotación, basta con revisar la lista de IPs de GH en https://api.github.com/meta. Cualquier IP que esté en las listas de 'web' y 'git' deberia funcionar.
Esto es en definitiva un problema que debe solucionar Movistar con su proveedor, pero dudo que haya alguien suficientemente interesado en los usuarios para tomarse el tiempo de resolverlo.