Pay for a VPN service that you can get a router to work with (so you can pass your XBox traffic through it). I've never used any but I know some that use Strong VPN. I have the same problem (am overseas with an APO). The problem is your overseas IP, not your billing address. A friend of mine flashed a router he bought with DD-WRT (www.dd-wrt.com/.../index) and Strong VPN uses a VPN setup that you can configure in DD-WRT.
If you aren't technologically inclined this is probably far more than you'd be interested in trying. If this seems like too much you can get an Amazon Prime account for free priority shipping to your APO (or pay shipping) and then just buy all your stuff through it (and waiting the 10-16 priority days).
VPN services can be as cheap at $6-8. They can also help you for things like Amazon Instant Video, Netflix, Hulu, UK content etc.
You *might* be able to get away with making the purchase on a US IP and then downloading from an overseas one. A friend of mine only tested a US IP and had the download routed through the US IP.