99.99% uptime is a lot to ask for and you may pay greatly to get it. that only allows for about 52 minutes of downtime in a year. Hardly even time to do a software upgrade and reboot. I don't have a problem with a host with 99.00% if the 1% is PLANNED during off hours. Also, don't believe uptime claims. I was with CIhost a few years ago who had an uptime guarantee. Their DNS servers went down for almost a week, and they claimed that since the servers were up (accessible via IP), but just could not be contacted by a domain name, they had met the uptime guarantee. Also evaluate if the claim is for the company, the actual server, and includes DNS and mail servers, the backbone provider, etc.
If you need absolutely no downtime, a better solution may be an inexpensive host with a mirror site on another inexpensive host in different parts of the country using different backbone providers, with backup DNS servers in separate places.
As for hosts, I recently evalauted several. my top 3 choices were httpme.com, voxtreme.com and weberz.dom. I chose the first one, but was happy with the prices, reputations, and services of all three. Although I was interested in reseller hosting with unlimited domains.