Time = credibility is not a good judge. There are a number of companies that have been around for 10+ years, and just as many smaller companies without the large marketing budgets that have been around 15+ years. Most SMALLER companies survive on quality service and support, where as many larger companies while they may provide good service, are often relying on investors and advertising.
1&1 is a fine example. They are not concerned with keeping clients for the long term. They get more money with a higher turnover than if they have to actually provide the services they offer. This is due to how their company was first established (not as a hosting company, but a marketing company). With their large budget, they can afford the 15 page advertisments in Computer Shopper and other publications and not even bat an eye. GoDaddy, another service that spends MILLIONS on advertising, and they are rewarded for it with their signups etc. They are not a one stop shop that fits the needs of everyone, but the average person on the web, they do just fine.
So if you have the investors you can easily brand your product on a larger scale and can also afford to LOSE money on a monthly basis. Most smaller hosting companies survive based on profit 😉