Besides the obvious backup power, cooling, environmental stuff mentioned above....
1. Expandability.. how much rack/cage space is available nearby? Get a right of refusal on any empty space near your stuff if you can.
2. Power max per rack, can you get enough for SAN's, blades etc
3. Remote hands availability/skills/costs (really want to make a trip to the datacenter to replace dead hard drives? No. Do the employees know enough to do *limited* work for you)
4. 24/7 access, near employees if a physical presence is required
5. What sort of racks do they have? Can you buy your own?
6. Storage space. Need 100 servers shipped but don't have racks yet? Need to keep spare hardware on hand? Do they have room keep that for you?
7. How many/what carriers do they offer? How is access delivered? What does their network look like?
8. Do they have spare tools/network cables/misc parts. Can they order stuff for you, or is there some place nearby you can pick things up if needed in a hurry?
9. How many employees can you get access for?
10. Do they have a crash cart? Comfortable place to work? Wifi or other forms of internet access available?