From the many posts I have read on this topic, the seasoned hosts have always recommended spending money on local advertising.
Normally it's left at that.
I did a little more probing to get some more info from them

and they suggested local areas such as classifieds, newspapers, magazines, local businesses, etc.
I'm not concentrating on hosting just yet (I'm doing web development and only hosting clients so far) but business has been slow lately and I'm considering doing this for my web development business and possibly just visiting several businesses in my area in person and inquiring about their needs.
Might be worth a shot.