First of all, IANASA but i play one on tv (not really).
It seems to me both sides are doing it wrong. I understand you can only put so much information on Ask Slashdot before getting ignored by the tl;dr crowd so I might be wrong as well. Anyways, here it goes:
1) You said "I have a heavily-hit public server (web, mail, cvs/svn/git, dns, etc.) that runs a few dozen OSS project websites...".
Too many eggs in one basket in my opinion. No wonder you are pissed about outages. It sounds like you have one beefy server capable of running multiple virtualized OS instances (encrypted nonetheless).
So why not just cancel your dedicated service and get VPS from multiple providers? That way you would have enough redundancy (e-mail, dns, rsync, HA/Varnish, whatever), none of the headaches of hardware/virtualization and save money while at it. Managing wouldn't be harder considering your proposition of vmware/uml. Also easier to move from your server bit by bit. Start with DNS, then e-mail, then web, then... You can take your time as it won't cost you much upfront (zero?) or monthly (sub $50) and gives you the ability to scale up or down the resources to acomodate the workload and cost.
2) You said "When I file 'WTF?'-style support tickets to the provider through their web-based ticketing system"
Do you have the option to call the provider? If not, you are doing it wrong. From my experience, over 80% of all ticket answers are canned responses. If possible, try calling (if you didn't yet) and get someone that has the power to fix the issue to talk to you. When you reach a dead end, ask to be transfered to the legal dept to discuss your contract/sla/whatever. If they don't have one, ask where you should send the legal papers. If everything fails, try the BBB.
Just my humble opinion. Excuse my poor english as it's not my first language.