Sim, você pode, dependendo da capacidade de seus gateways permitir a configuração.
Você configura uma regra NAT no gateway para manejar o endereço de origem do tráfego VNC para um endereço IP do gateway local no caminho (ou, mais especificamente, no Linux, no caminho de saída da sua interface interna).
É bom usar um endereço IP alias (ou pool deles) na interface gw para que você possa identificar e separar o tráfego desconfigurado do normal. Separe um endereço ou sub-rede que esteja no espaço de endereço local, mas tratado como um endereço externo de confiança sábio, digamos 10.56.9.254
Além disso, o registro em log antes do NAT é útil para que você possa identificar de onde o tráfego realmente veio, já que sua caixa VNC agora verá um endereço interno local para todas as conexões.
Quando o tráfego chega ao VNC ele vê um endereço de origem local que sempre será roteado de volta onde quer que você tenha atribuído (o tráfego nativo originado de) então o tráfego voltará para fora do jeito que ele entrou e será -desloucado ao sair.
No linux world, o endereço e a regra nat serão parecidos com:
ip address add 10.56.9.254 dev intnic0
iptables -t nat -A POSTROUTING -o intnic0 -p tcp --destination 10.56.9.vnc --dport 5900 -j SNAT --to 10.56.9.254
Você pode fazer o mesmo no outro GW com outro IP, digamos 253 e então você pode se conectar através de um ou outro.
Se você passar pelo processo de conexão, isso é essencialmente o que seu NAT está fazendo ao sair de sua rede interna. Modificando o IP de origem, enviando os pacotes e mapeando-os de volta quando os pacotes retornam. Você só quer fazer isso para uma conexão específica e na direção oposta, que é onde entra a configuração do gateway. Ela permite configurar o que é capaz?
edit: você pode implementar as mesmas regras de NAT no padrão GW 10.56.9.5 se você direcionar o tráfego VNC via 10.56.9.5 e puder identificar a internet de onde os dados vieram. Talvez através da marcação dos pacotes no caminho através dos gateways ou no gw padrão, onde você ainda pode dizer de onde os pacotes vieram.