My rommmate's been complaining about problems getting Halo 3 to work properly with NAT, and I had a very difficult time finding information about how to solve the problem. The XBox360 labeled my NAT configuration as “moderate” with no explanation about what that means. Bungie's recommendation is to buy a new router.
Eventually I was able to figure it out, but Google searching was very unhelpful, so I figured I should share my results here. Assuming you only have one XBox360 on your LAN, you'll need to assign it a static IP (I prefer to do this by configuring my DHCP server to assign a particular IP based on the client's MAC address), then set up port forwarding. The ports used by XBox Live are:
Here's how to do it with a Linux-based NAT router:
iptables -t nat -A PREROUTING -p udp -i ethX -d 220.127.116.11 \ --dport 88 -j DNAT --to 10.9.8.7 iptables -t nat -A PREROUTING -p tcp -i ethX -d 18.104.22.168 \ --dport 3074 -j DNAT --to 10.9.8.7 iptables -t nat -A PREROUTING -p udp -i ethX -d 22.214.171.124 \ --dport 3074 -j DNAT --to 10.9.8.7
...where ethX is the WAN interface, 126.96.36.199 is the WAN IP, and 10.9.8.7 is the internal IP address of the Xbox360.
Once I was able to figure these out, I found MSKB 908874 which does at least list these.