Prueba haciendo un ping al dominio que te da problemas, apuntas la ip y la escribes en el Internet explorer:
http://ìp_del_servidor
A ver si funciona de esta manera, lo cual demostraria que el problema lo tenemos en el DNS del ISP, que tarda en actualizar los registros seguramente.