EDIT: I will expand on this a bit.
First, the real question you need to know, is, who owns the building your servers will be in? Lots of people claiming to have datacenters are actually renting from someone else, or even sub-leasing from somewhere else, putting you 2 places away from the owner. As much as possible, get into a situation where your monthly payments go directly to the true datacenter owner.
Second, what about the network? Rather than engage in a lot of hand-waving, just find out who they are directly connected to.
Third, do they have both UPS and diesel genset backup for your power? If you are able to physically visit the place, have them show you the physical stuff.
Ignore the "Tier" datacenter and "SAS70" crap, Tier X != reliability and SAS70 is a load of BS (CPAs trying to soak up some consulting dollars - yes, an SAS70 report can only be prepared by a CPA firm...)