Thanks for the pointer, I haven't considered that approach (mainly because there already were ideas about a relay server, I think).

The problem we are having is that connections incoming from a computer over the internet to local hosts are blocked by NAT or by firewalls. The reverse direction is normally permitted: A local host can have outgoing connections to any server in the internet. So we need some way to punch through the NAT/firewall from the outside to reach the locally hosted game.

We are intending to set up a relay server which can be reached by outgoing connections. Since those are always possible (okay, maybe not in some company networks or so), the clients and the game host can connect to the relay. The disadvantage is, that we have to provide such a server and the network/computational load of forwarding packets.

Their approach (well, the approach they are planing) does not use a relay server. They also need a special server for it, but only to transfer some initial messages between the participants.
The idea is that the host tries to connect to the client, which will most likely fail. But by doing so the host "punches holes" into his NAT since the NAT has to allow answering packets from the client (which won't come in this case, but the NAT doesn't know this). Now the client tries to connect to the server, which will now work since we punched the holes, making the server reachable.
So much for the nice theory. Unfortunately, NATs often change the port of the outgoing network packet. For example, your computer might send a message to a webserver and thinks that he is sending from port 51253. But since the NAT changes the port,the webserver sees another port, e.g., 55742. The same happens in our host/client combination. Here it is even more fun, since this happens on both sides of the intended connection.
That is where the special server comes in. Both host and client connect to it and the server tells them which port he sees the other is using respectively. So when the client tries to connect to the host, he is not using our normal widelands port for it but instead some other port the NAT selected. And now comes the bad part where it breaks: For each new connection (first connection: host to special server, second: host to client) the NAT selects another port. So the client can not connect to the port the special server is seeing but has to connect to some other port. Some NATs behave nicely and select easily guessable ports, e.g., simply increasing. Others are using random mappings so there is no chance that the client guesses the right one.
Compared to the relay server, this approach has the advantage of less load on our servers. The disadvantage however is, that there is no guaranty that a connection can be created.

They already seem to use UPnP as another approach. With UPnP it is possible to automatically establish a port forwarding in the router, which would solve the reachability problem. Unfortunately, this is not enabled in all routers so it won't always work neither.

So we could follow (one of) their approaches but when we want to guarantee a connection we have to offer a relay server anyway. At least, that is how I understand it. Of course, we can offer a relay server and one of the other approaches, too, in the hope of reducing the load on our server.
Hope this is understandable. Any remarks or corrections are welcome.