Limpe o cache do DNS em sua máquina. Este é definitivamente um problema em sua extremidade, não no Azure. Aqui está um guia para diferentes sistemas operacionais.
Com relação à alteração de IP, isso acontecerá na maioria das vezes em que você encerrar / iniciar suas VMs, já que os endereços público e privado não estão reservados. Se você precisar corrigir o IP para seu serviço de nuvem da VM, verifique este guia:
Defina um endereço IP interno estático para uma VM
UPDATE: Outra razão possível é o cache DNS do seu provedor de internet. Pode levar horas para atualizar. Se o problema acontecer novamente, tente verificar o que é o ip retornando do servidor DNS do seu provedor usando este comando nslookup:
C:\WINDOWS\system32>nslookup myhost.cloudapp.net