There is no need to reinvent the wheel actually because the folks who decide to buy hosting products, have either seen some ads about the company, either in AdWords or on a page or when searching Google organically and finding the listings, or the links on some blogs, forums and directories. In the first couple of months, everything might turn out to be so time-consuming and tedious, not generating conversions.
Although you may experience a ton of hits and page views, you still may not be able to persuade customers of an old, world-famous firm to shift to your newly launched web company but don't get disappointed. An egregious mistake would be to target the whole world, burning cash on advertising on terms like "web hosting" which although may generate page views, will not help you sell.
Choosing long-tail keywords right from the beginning is a winning strategy even in the world of SEO. For example, even if you spend tens of thousands of dollars in cash on your SEO, you may not reach the first page of Google for the term "web hosting" but with a fraction of spending and choosing the better term "affordable web hosting in Ohio" you could see many customers within weeks.