Supongo que tu proveedor de acceso es telefonica y tienes contratado el adsl. Recientemente han instalado el famoso proxy-cache que hace de las suyas. Puedes encontrar más información aquí:
http://www.caravantes.com/arti03/proxy2.htm
Tu proveedor de hosting no es el culpable de estos problemas, pero entiendo tu molestia. Prueba a acceder a tu web desde una conexion dial-up por ejemplo y verás que tu web ha sido actualizada correctamente. La verdad es que no está muy claro porque afecta a unos proveedores y a otros no...
Suerte con tu web!!