I am always surprised Rackspace Cloud Servers are left out. We've been using them for over a year with only a handful of outages (VM host reboots- 3~5min each).
For us it is worth the price (>$40/mo for 1 GB ram) for great stability and support. The Openstack API is really nice, too.