Maybe a little late, but
www.escapedturkey.com is (I think) the cheapest game server hosting you can find anywhere on the internet. I rent a server from them, 35 player slots for $25. 45 for $35, 55 for $45, 65 (dunno what games support 65) for $55. The performance is good, its cheap because its run by one guy, which means no official tech support, just forums. There's been some downtime recently though, ET has been switching to dual dual-core Opteron boxes with 8GB of RAM, then there were issues with the hardiness of the power strips being used for such monstrous boxes. Things seem to be smoothing out now.