Manejan sus propios DNS?.. alguna ves tuve el mismo problema ya que mi proveedor de servicio manejaba algunas DNS como primarias al igual que nosotros.. eso fue un caos.
Algunos DNS demoran cierto tiempo en refrescarse segun la configuracion que se tenga para que se replique a traves de la red.
esta pagina me sirvio bastante para probar los dns desde fuera de mi red
http://www.network-tools.com
saludos!