(we do more site development than domaining, so the hosting reflects that)
Been with Rackspace (dedicated, now with some sites on their cloud) for nearly 6 years, expensive but their network is fast and support is good (would have been excellent support but we have had a recent problem).
We also have cloud servers on Amazon Web Services for large scale data processing (to keep the web servers as speedy as possible). They can be very economical for occasional use (or even full time use if going with reserved instances) but I've not tried hosting sites on them.
As is probably known by many, avoiding 1and1 might be a good strategy... we're about to move the last of our stuff away from there soon - stuff that was not a priority.
Planet/EV1 servers were also problematic for us when they combined a while ago.