What you really need to host a game is a virtual machine in the cloud.
A "VM in the cloud" is just an "instance" of an O/S running on some hardware on some server that has good internet connectivity. Multiple VM's can run on the same piece of hardware, (but that isn't a concern to you as the consumer). They promise you availability of certain minimums of CPU power and RAM usage. For all intents and purposes though you just have got a remote machine that you can SSH into (or Remote Desktop or whatever).
There are 2 major providers that I know of (others please feel free to add more) that offer reasonable prices.
1) Amazon Web Services' EC2 (from $0.02/hour). There are a lot of configurations to choose from, but if you don't even have an Amazon account yet, then that's good because you can get free use of a "micro" instance for 1 year (1 year is from the date you sign up, not from the date you kick on your first server).
If you've already had an account for a year, prices are around $0.02/hour. For a Linux "micro" instance. So in one month, that totals about $15 (744 hours/month).
2) Windows Azure (from $0.02/hour) offers both Windows and Linux VM's for the same price. If you want to program with Microsoft technologies, Azure is worth a try (I'm not sure about QOS vs Amazon) but it definitely seems the licensing premium is lower when you go through MSFT directly instead of renting a Windows box from Amazon.