Just some thoughts.
Go to the company that OWNS the data center. This is a preference thing for me, but if you go to a company that is leasing space in the data center and then re-selling, you have 2 levels to go though if there is an issue and likely you can't even talk to the real owner of the data center. I prefer to deal with the true owners. There are plenty of companies out there that work by leasing space and do a good job but this is my preference.
Make sure the contract indicates you own your equipment. If the company goes out of business, you want to be sure you can get your equipment back, even then it might not happen. This relates to the top one, if the company leasing the space from the DC doesn't pay their bill, all the equipment might be seized including yours. This happened to me, lucky the main company knew this and contacted us (and the others I assume) and we were able to do a contact with them.
Consider less obvious locations. Cable companies for one. They are doing VoIP services now so they need huge bandwidth, but are not using it all. They need to have really high SLA for their cable customers and the VoIP so they usually have a really good setup. I got a good deal at one, paying about half of what I would have at a high end place. The only downtime they had is when about half the internet became flaky.
If you are going local (thats what I prefer) get a tour. See it and what they will give you. Sometimes you can get a better deal. With the cable place I actually was able to negioate.
If you can, put one server there (a non critial one) for a month or 2. Make sure everything is good. The place may put up a good show when you are there but then you find out their sevice sucks, or even worse is down a lot. This one I learned from a bad experience.
Since this equipment is out of your control physically make sure you can afford to lose it. It shouldn't happen, but it could. So have a disaster recovery plan in place so that if your server suddenly go offline and you can't get into the place to get them back (or fire, flood, etc) you have a way to bring up servers at your own office in the interm. VM is great for this.