Server Beach
was recommened to them by a frienda couple of years back, never had any problems. I think they were originally created as the budget division of Rackspace but now they've been bought by Peer1
No downtimes, No Worries.
I've heard good things also about ServerMatrix but never hosted there