To answer your questions:
1- I'm not sure. The best is to ask your prospective customers.
2- That's a good question. Can you make something better than SEOMoz by specializing? Your initial Unique Value Proposition is that it's easier because the domain and keywords are known. However I don't see that as being much work. Can you quantify that?
3- I think your initial reasoning for choosing the industry is right.
4- no idea. Google searches, reviews sites would only cover a small part of all hosting companies.
5- Contact people directly from LinkedIn or from contact forms on their websites. Try to get smaller hosting companies first (for e.g local hosting companies in your area).
In the end, I'm not really sure about the value of what you're offering. If you could service one niche, you could trivially expand (it's just a matter of entering keywords). So your product needs to have some more niche relevance. Maybe a list of link building tips, bloggers to reach out to do guest blogging, industry-specific opportunities etc.
If you want to brainstorm this more, I'd be glad to help. My email address is in my profile.