I'd recommend looking around locally in your city/region. Lots of cities have small, well-established companies that do a grab-bag of MSP, IT, Microsoft hosting, and offer some VPS or colo. They're usually on the expensive end but they come with the benefit that they've usually had their IP space for a long time and manage it carefully (unlike basically any "modern" provider), and since they're in town it's usually easier to get someone on the phone if there's a problem. Make friends with the people who run these kinds of businesses anyway, in a lot of smaller markets especially there's a bit of an informal club of IT service providers and if you chat with them regularly you'll end up getting good advice and business leads. I've had a colo inquiry to a local company turn into them sending me one of their clients before just by being chatty with the network guy.
