1st battle.net (warcraft 3) should work without issue on most NAT configurations but may need some ports opened.

The following ports are required for Playing games on battle.net (warcraft3)

4000 TCP.UDP and 6112-6119 TCP and UDP

If your buddy uses broadband and uses an Internet sharing device, you will have to
have the above ports open on the firewall/router and have the traffic forwarded back to
the workstation running warcraft 3.

Windows NT 4.x does not include a firewall. As some have stated, a 3rd party software
firewall may be running..Make sure you check that.

If it turns out to be an issue with a router/firewall device, post the make and model and we can offer suggestions about configuration.