I think every single host I have ever used claims 99.9% uptimes, but never do any get close to it. If you want uptime get hosting with a 100% SLA (might mean VPS or Dedicated).
What I don't get is why you didn't try e-mailing them, or raising a ticket, first? Not sticking up for them as they sound like cunts, but everything else you tried seemed to be so much more time/expense/effort than a simple e-mail would of been, in fact I find it much easier to write the problem down as it can be difficult to explain it to someone over the phone - especially when they dont have a clue.