Not endorsing these guys since I have no idea what their availability is in practice, but isn't 3 nines a fairly common SLA? I believe this is what I get at Linode and Digital Ocean.