The Hustle is key, relationship building, word of mouth are all key options for building your brand and clients. Another option is to build your connections of web developers/designers. Offer them free hosting for their website in exchange for using your services for their clients. It's tuff for the avg user to know where to turn with so many options and so many levels of pricing. Because it is so easy for someone to set up shop, there are boatloads of web hosts that price them self's so low as to think that they will be king of the hill, without stopping to understand gross profit and the time it takes to maintain your clients. Striving for longevity, that you are reliable and you are in this business for the long haul may be helpful as well. But as you can see with the OP's web site now out of business or offline, it is not easy.