We use MT's Dedicated Virtual offering - it's "in the cloud", but it gives us full on root access. If you go that way, however, get a box without Plesk pre-installed. Ugh.

I'm going to have to agree with the MT route.

I joined up recently, and they're fantastic. Handle spike traffic well too :)

I'm on a (dv) extreme. very powerful box, excellent service.

Same, don't get much traffic yet but when I do MT should handle it fine.