Hast du die Ports auch beim Router freigegeben (Standard: 3979 TCP und UDP)? Zudem muss die Firewall nicht deaktivieren, ein öffnen der Ports sollte genügen. Möglicherweise hilft es auch, wenn einer von euch beiden den Standardport ändert (in der openttd.cfg unter server_port) und dann natürlich auch diesen Port freigibt.

Wenn sich jemand nicht im Netzwerk befindet muss über Internet gespielt werden. Dazu muss "Internet (ankündigen)" ausgewählt werden und nicht "LAN/Internet".