i had the same issue with my linksys wireless modem router before. tried portforwarding and all the possible settings, but i still got a strict NAT. i guess some routers arent 100% compatible with xbox live.

finally i gave up and just dmz-ed my 360 and the NAT is always open now. like some have said here, putting yr 360 in the dmz is relatively quite ok.