XBox Live, NAT, Strict vs Moderate vs Open
I've been having trouble joining Call of Duty 3 games with friends, and went digging to figure out why. Turns out it was my router's firmware.
I have a WRT54G v2.0 router, and I've been running the HyperWRT firmware since back when I was fighting with trying to get good quality of service for voice calls with Vonage.
Many forums tell you to get XBox Live working over a router all you need to do is forward UDP port 88 and both TCP and UDP on port 3074. But it's not that simple - that didn't fix it for me. I had UPnP turned on, had those ports forwarded, but the XBox network diagnostic still said Moderate for the NAT.
I found this excellent page that describes the difference between cone and symmetric shapped NAT, which is very interesting reading, but didn't really answer the question. But I figured this might be one of the differences between HyperWRT and the default Linksys firmware, so I updated to the latest firmware from Linksys (http://www.linksys.com/download/) and lo and behold, that fixed it.
The Microsoft Compatible Home Networking Equipment page is actually useful here - it shows which routers they've tested and know work.