Have you checked Rackspace cloud? They are extremely cheap comparing to other cloud-based solutions.