Well, so our magic formulae is:
history of the hosting company(how long it's been on the market)+flexibility of the package( your ability to change configuration whenever you need it)+quality of the support. Haven't I missed anything important?
The only thing from the previous posts that I object to is the number of clients. Nati wrote she'd checked up this beforwe deciding on her host. I don't think this number of clients/quality relation is directly-proportional.