http://www.hetzner.de/ quite solid and have great prices too.
I haven't measured it, but they're probably within the 99% availability (allows for 1.68 hours/week downtime) they advertise for any one machine.
Maybe my expectations are too high. :)
Never had any problems during our partnership with them, which we started 4 years ago.