I had bad experience with Rackspace Cloud.

With Servint and Mediatemple DV for the past couple of years and didn't have any major issues to complain.