I have a good relationship with Interliant's dedicated server support and can contact them via AIM when there's a problem. (It also helps that I alert them to new issues on this list.)
I'm also with Interliant. One of the best things about them is the tech support. You can always get a live person with minimal wait time (plus a 1-800 number) and they'll stay with you until the prob. is fixed.
Additionally, I had some intermittent network problems a couple months ago the worst of which was about 4 hrs of on again off again connectivity during a time they were experiencing some sort of DOS attack. I called to complain and they rebated the entire monthly server fee without a hassle. Additionally, they has someone follow up with me from customer support to ask if there was anything else that could be done for me!
As has been said many times before, "you get what you pay for." I don't mind paying a little extra for this kind of service.
Brian