GoGrid lets you mix and match dedicated and cloud servers, which offers the performance and value of a baseline of dedicated, and the flexibility of the cloud. I find it to be unparalleled.
Softlayer (my preferred dedicated host for years) does this as well. I agree that it's currently impossible to beat the combination of bare metal performance and cost efficiency with the ability to spin up cloud servers within one's own VLAN.
Rakckspace just launched something called Cloud Connect, which I believe does the same thing.