You may want to look into getting a dedicated server or leasing one and shipping it off to a local server collocation center. Servers are pretty cheap nowadays. You can lease a good one for about $100/month, so if you got a couple friends/partners onboard, the costs could be very reasonable. I looked into this myself about a week ago for other reasons (not wanting the compromised performance of economy hosting).
If you choose to go either the dedicated server or server collocation route, don't fall for their marketing -- an entry level server (even a weak celeron) will more than be able handle the traffic that you and even a couple other businesses will be able to throw at it, provided you stay away from mega-bandwidth, ultra high processor intensive tasks (ie game servers, "mini-YouTubes").