Teoricamente, todos devem ver o registro A atualizado em algum lugar entre instantaneamente e o valor TTL relevante. A maioria dos registradores definem o TTL para 24 horas IIRC, então por 24 horas algumas pessoas verão o endereço antigo e algumas verão o novo, e 24 horas depois da mudança todos terão o novo endereço, com alguns usando um valor menor como 4 horas.
Se você tiver acesso para alterar os valores de TTL (ou seja, você executa seus próprios servidores DNS como eu), então você pode reduzir os TTLs para algo menor um dia antes de fazer a alteração, portanto o período de propagação é muito menor .
Eu digo "teoricamente" acima, pois sempre haverá alguns bugs, falhas e caches mal configurados por aí, o que significa que alguns usuários não verão a mudança por mais tempo. Isso é especialmente verdadeiro se você usar TTLs muito pequenos, pois ainda existem alguns ISPs com caches DNS que ignoram TTLs abaixo de um determinado valor.
Outra coisa a observar é o atraso entre o painel de controle DNS do seu registrador e seus servidores DNS. Por exemplo, notei que as alterações feitas em domínios gerenciados pelo 123-reg.co.uk podem levar até uma hora para aparecer em seus servidores DNS, o que é uma hora a mais em relação ao valor de TTL que você deve contabilizar .