How do games handle NAT router problems?

For the past few days I've been working on an online game, a 2-player game where one starts a server (listens on a certain port) and another one connects to him by entering his IP. There are two problems with this method:

It is very uncomfortable to input the opponents IP.
The server must not be behind a router, because the NAT prevents it from working.

The first problem can be solved with a matchmaking service that takes care of the IP addressed without the users' concern. But I am not sure how I can solve the second problem. I have read about "TCP hole punching", but according to what I have read, it is not possible to perform this when both players are behind a router. If that is true, then how do games with matchmaking services like Halo 3, where one of the players is the host, work?

Thanks in advance.

Solution

You could use a technique called UDP Hole Punching, for gaming UDP might be the better choice anyway. But you still need some sort of rendezvous server to enable the initial handshake of the clients.

See here for general information