In addition to looking for a host for myself, I also need to make some recommendations for others. Consequently, I am very interested in reliability claims -- I'm not above doing a little CYA.

What hosts in the reasonable price range (i.e. sub-$30/month) have some substantiation for their uptime claims? Anyone can claim 99.5+ uptime (heck I'm on a diet that often), but do any offer any third party validation?

Well, 3rd party verification would mean there's another server somewhere which has the potential of being down, or network being down, etc., and I'm not sure how many companies would put their refunds in the hands of something like this. Your logs should be a good indicator (usually there aren't a whole lot of entries if the server is down for a period).