Unfortunately it seems that you have covered the basics correctly. I would try two other things, try it with UPnP disabled, I vaguely remember this being an issues with Linksys routers so maybe it will apply. The second is that you can put the xbox into the DMZ. I can't seem to find any instructions on this, but it should be fairly straight forward.
On a side not I imagine that when you say you configured the Static IP that you did this on the xbox and not just the router. Sorry I know its a stupid question, but I have to ask because it looks like you did everything right.
I did notice on the bottom of the 'portforward' link, there is a tool that says it will allow you to confirm that you have ports opened correctly - maybe that will help out? I'm not sure about the quality of the software and/or entirely how it works - but it may be another tool in the toolbox.
I had a similar situation to this a few years ago - I remember our analysis made us start to think that it may have to do with the source port as well (does Xbox require the query to come from a certain source port?). I'm not sure about this - can anyone comment?
Any information or lessons learned, Larry, please be sure to let us know!
Table of ContentsIntroductionVersion HistoryPossible Future
UpdatesDocuments PurposeNAT Operation in ASA 8.3+ SectionsRule Types
Network Object NATTwice NAT / Manual NATRule Types used per SectionNAT
Types used with Twice NAT / Manual NAT and Network Obje...
Table of Contents Introduction:This document describes details on how
NAT-T works. Background: ESP encrypts all critical information,
encapsulating the entire inner TCP/UDP datagram within an ESP header.
ESP is an IP protocol in the same sense that TCP an...