This sounds like a strange networking problem wherever you are trying to connect from, not necessarily a problem with Xbox Live or the games you are playing. If your router has an option to put your Xbox in the DMZ, that might help as you will be opening your NAT completely for a single IP address. Just make sure it is static and that you aren't picking up that IP on a different computer.
There are a million FAQs that try to help walk people through how to make sure their networking is set up correctly but it sounds like you have been through all that. I'm thinking either:
A) The internet connection you are playing on just won't support an open NAT, regardless of what you do. Security settings that are outside of your control = bummer.
B) You may just need to change your networking hardware or firmware. This too is a bummer because it is hard to set up correctly, or costly.
I wish my post could be more helpful. Hope you figure it out man...