I used to use serverbeach. They are definitely not cheaper if you compare RAM to RAM (just under 2x the cost of EC2 reserved), but of course they're dedicated not VPS, which is a better offering... not sure how much more their cheapest dedicated boxes are worth in comparison to an ec2 small instance though.