I've had great results with amazon cloud servers? Not sure what the costs on that would be though since I never saw the bills; but excellent stability and you can customize for whatever resources you need the most.
There is also a co-location hosting provider in downtown Toronto that quoted me $99/month for a 1U rack server, 1 amp power supply. You pay a little more upfront since you need to come with your own hardware, but a cheap AMD 16 core server can be had for a thousand or two last time I built one.
In case any of that helps... Nothing like putting out a fire with everyone suggesting "helpful" ideas