Você pode usar o DNS dinâmico. Instale um cliente DNS dinâmico em cada um dos seus servidores e o IP será atualizado quando for alterado.
Você terá que configurar o Nagios com nomes de host em vez de IPs. Provavelmente você deseja um TTL baixo no servidor DNS para evitar que o IP antigo seja armazenado em cache por muito tempo.