I don't know if this helps, but...
I play Doomsday on my LAN with my stepdad, and it's alot of fun. We wanted to play it with my step-uncle as well, but after almost four hours of technical troubleshooting, we gave up. I've tried everything listed in this thread, and none of it works. We were about to give up on playing HoI on the internet, when I had an idea:
Run a network traffic logger on my computer as I host a perfectly bug-free LAN game.
We fired up a quick LAN server, let 10 days run by so we knew it would work fine, and then I did a manual scan of the traffic. This is what I found:
On our LAN, only three ports were used: UDP 47624, TCP 2300, and UDP 2350. Since we didn't try chatting, it's entirely possible that for in-game chat to work, another port is used. But, for hosting a LAN game, these were the only three ports used. I would ASSUME that in Direct-IP games over the internet, more are used, and in Valkyrienet, even more ports are used. But, forward these three ports, and it should work.
The thing is, and this is very very strange, is that, apparently these ports have to be forwarded on EVERY COMPUTER PLAYING THE GAME. In a normal TCP connection, your computer sends a packet to a port on another computer (for example, TCP 2300). But, your computer also needs to specify a port to receive the reply to that connection. This port is usually chosen at random (in my network traffic scan, it was something like TCP 41902). The thing is, the router/firewall will AUTOMATICALLY let this traffic through because it is a reply that you are expecting. This is why, in most normal games, you only need to forward ports on the server.
In the network scan, what I noticed, however, is that, in addition to a TCP connection from my stepdad's computer on TCP 41902 to my computer hosting a game on TCP 2300, is that my computer, hosting a game, initiated a connection to my STEPDAD's computer on TCP 2300, with randomly(?) chosen port 4672 as the source. This basically means that the client and the host are having two simultaneous conversations at once; but we are all only allowing them to have one (when you port-forward TCP 2300 on the host's router). Also note that, since the host started the second TCP connection, it expects traffic back on TCP 4672 and therefore you do not need to allow for that.
This solution seems VERY strange to me, but then again, I have always had problems playing DirectPlay games on the internet through NAT, and DirectPlay was originally developed before NAT routers were widespread. Finally, it does seem to explain all the issues that I've seen with this game.
The fact that some people are having success with forwarding ports only on the host's router: many routers and router-firewalls work different ways, and often the ways are cryptic and counter-intuitive (my stepdad once spend a month trying to figure out why he couldn't host a server of a different game, eventually finding out that his router's "gaming mode" was in fact the PROBLEM. He actuall yhad to buy a different router to make the server accessable). Some routers may simply look at the second TCP connection from the host and say "hey, I'm expecting traffic back from this guy" without actually looking at the PORT from which it is originating. Other routers, such as mine, would say "yeah, I'm expecting stuff from this guy, but, not on this port. DROPPED".
Anyway, I do want to finish this port by saying that we have not ACTUALLY tested this solution yet. However, within a week or so we'll find out if it works, and I will come back and post my results.