Claro, esto es problema de cache, muchas veces esto queda en la configuración de tu proveedor de internet, lo que a mi me ha funcionado en estos casos es utilizar DNS's públicos, son bastantes sencillos de configurar y muy eficientes, ademas que tu velocidad de internet aumenta considerablemente.
En lo personal te recomiendo utilizar los de Google
https://developers.google.com/speed/public-dns/