O registro é delegado dos servidores de nomes principais - é como uma cadeia (ou geralmente descrito como uma árvore inversa). Todo cliente DNS conhece os endereços IP dos servidores raiz - esses são um conjunto de servidores (acho que é 13) que forneçam os endereços IP dos servidores dos registos - Nominet for .uk, eurID for .eu etc.
Seu domínio é então registrado no registro que possui os endereços de seus servidores de nome (ns1.oldserver.com no seu exemplo). Finalmente, o servidor de nomes do seu domínio (ou servidores de nomes como você deve ter no mínimo dois) atende a solicitação real.
Imagine, por exemplo, um cliente quer visitar www.domain.com.
Isso pode ser dividido em três componentes - o chamado domínio de primeiro nível (TLD) para o qual o cliente consulta os servidores raiz - .com neste exemplo. Um dos servidores de nomes que serviriam a isto pode ser a.gtld-servers.net - os servidores de raiz darão o endereço IP de a.gtld-servers.net ao cliente - estes são conhecidos como registros NS e de cola.
Em seguida, o domínio real - domain.com neste exemplo. O cliente consulta a.gtld-servers.com para domain.com. Isso pode, então, devolver os endereços IP relevantes ns1.domain.com e ns2.domain.com aos registros NS e glue.
Finalmente, o nome do host - www neste exemplo. Portanto, o cliente consultará ns1.domain.com ou ns2.domain.com para o domínio www.domain.com e recuperará o endereço IP real do site (registro A).
Tudo isso ocorre em milissegundos. O tempo limite típico para um resolvedor de DNS é de 2 segundos.
Para voltar à sua pergunta original, quando você altera os servidores de nomes, você está alterando os registros do NS no nível do registro (Nominet, eurID etc.) Depois que a alteração é feita, quando um cliente consulta os servidores raiz por domain.com, ele receberá o endereço IP de ns1.newserver.com em vez de ns1.oldserver.com.
Normalmente, são necessárias até 72 horas para que todos os clientes em todo o mundo percebam a alteração, pois armazenam em cache todos os resultados por um período de tempo especificado no registro de domínio. Os registros NS geralmente são armazenados em cache por 72 horas ou até uma semana. Portanto, não deixe seus antigos servidores de nomes off-line por pelo menos alguns dias após fazer a alteração.
Alterar um registro A é o mesmo que alterar um registro NS - você só está alterando o conteúdo, como alterar um registro do banco de dados. A próxima vez que alguém consultar seu registro, ele receberá o novo valor (novamente considerando o armazenamento em cache, mas é muito menor para os registros A, geralmente de 1/2 a 1 dia).
Se você tiver acesso a uma caixa do Linux, execute o dig + trace www.google.com e verá toda a cadeia de consultas que podem lhe dar uma ideia melhor.