I just finally got around to checking out Amazon's EC2 (Elastic Compute Cloud). This service, that is currently in limited beta, looks very interesting.
Essentially what Amazon is offering is a Virtual Dedicated Server on top of their S3 storage service. This service seems like it could be an option for someone who is looking at a dedicated server. The prices are competive. (If you assume no data is transmitted or received, running one of these server instances would cost $72/month. the rate for data transfer is $0.20 per GB.)
I wish they offered an alternative pricing scheme. Currently for Amazon's S3, you pay when data is transferred. Something similar could be done for EC2. I would imagine a flat fee for every instance, and a charge per CPU hour actually used on each virtual server.