Nie pisałeś o drugim NAT.
Dwie wersje:
* Jak uda się na którymkolwiek NAT zrobić przekierowanie portu - robisz za nim serwer OpenVPN i łączysz się zza drugiego.
* Jak nie da się zmodyfikować żadnego NATa, to potrzebujesz trzeciej maszyny - z publicznym adresem, i na niej odpalić serwer OpenVPN. Z nim łączysz się z obu komputerów (win i lin) i wykorzystujesz routing między klientami.
Można też inaczej:
* Na obu maszynach odpalasz miredo/teredo (tunel IPv6 z dynamiczną adresacją) - i jak poznasz adres IP jednej strony, to bez problemu połączysz się z drugiej (UWAGA - to wystawia obie maszyny na publicznej adresacji IPv6! Trzeba dobrze ustawić firewalle!).
* Jak uzyskanie adresu jest kłopotliwe (ktoś musi się zalogować lokalnie i sprawdzić, albo musi wysyłać bieżący adres IP na maila/SMS), możesz załatwić tunel IPv6 (np w Hurricane Electric, SIXXS), co daje stały i publiczny adres IPv6.