Na verdade, descobrimos que a resposta mais fácil ao colocar um telefone atrás do NAT para conectar-se a um servidor Asterisk em um servidor público da Internet é definir o tempo limite do registro SIP para menos de 120 segundos (geralmente 100 segundos). Isso garante que o NAT esteja sempre encaminhando a porta de volta ao telefone. Ele também garante que o endereço IP privado do telefone esteja sempre atualizado nas configurações de NAT e, basicamente, que tudo "simplesmente funciona".
Outros esquemas como o STUN também não funcionam tão perto, e esta solução é realmente bastante robusta.