Se você puder instalar programas na outra máquina, uma maneira fácil seria configurar esta máquina para publicar seu endereço IP como uma entrada dns.
Por exemplo link (não gratuito) e link parecem ser dois programas que fornecem esse serviço.
Por exemplo, com dyn.com você pode instalar um programa que é executado como um serviço na outra máquina que manterá atualizando a entrada dns para, por exemplo, yourname.dyndns.org.
Se você quiser saber o endereço IP atual, você pode simplesmente pingar yourname.dyndns.org.
Em alguns casos (por exemplo, acessando um servidor da Web), você pode usar o nome diretamente e nunca precisar saber o endereço IP.