O termo NATs não-bem-comportados está incorreto - qualquer dispositivo NAT que use PAT (tradução de endereço de porta) para agregar múltiplos endereços privados a um único endereço público irá mapear novamente as portas de origem. Isto é o que "Endereço da Porta" refere-se ao PAT.
Seria impossível para dois dispositivos internos usar o mesmo endereço de origem para o mesmo destino e esperar que a porta de origem permanecesse a mesma após o NAT, e isso não beneficiaria a postura de segurança de tentar manter a porta de origem consistente ao segmentar vários destinos. Portanto, isso geralmente não é um objetivo que os firewalls têm em seu design.
Isso não ajuda aqui, é claro, onde você quer saber a porta de origem de uma conexão, sem realmente receber nenhum pacote dessa fonte. Um relé é a opção óbvia em que os endpoints se comunicam por meio de terceiros (sim, um relay apenas transfere pacotes entre soquetes como você sugere - a implementação é provavelmente muito mais complexa dentro dos servidores do skype, mas em princípio é a mesma).
É difícil ver como você poderia fazer isso de outra maneira, já que os endpoints não estão cientes das traduções que acontecem durante o vôo, então eles não podiam nem mesmo comunicar qual é a porta de origem deles através de um canal lateral de alguns tipo (como registrar apenas a porta com um servidor central, mas se comunicando diretamente).