It's best to check when a company established first. The company history usually can indicate whether they are realible enough. Then, ask them to provide a demo or trial of service. I ever used Database Mart's VPS to host my website. I think they are good.