Company of Heroes is a brilliant game – very strategic, realistic and affectionately developed. But since the version 2 (Opposing Fronts) came out, there were many complains about one error message appearing if you wanted to connect to a multiplayer game.

"NAT Negotiation Error"
or in german:
"NAT Verhandlung gescheitert"

I don’t know what exactly went wrong, but I had this problem too. My colleagues didn’t (they had newer routers).
I lived with the fact that I wasn’t able to play the game for years. But shortly I found the problem: Heureka! It is the Relic Downloader, running in the background and checking for updates. I minimized the game, killed the Relic Downloader Task and could play Company of Heroes

There’s just one downside: My friends aren’t on CoH anymore

Consequence: Relic seems to be incapable of developing runnable games, since so many complaining voices disappeared unheard. They could have fixed the bug if they wanted. I am sure about that!