I have found that for my niche market, advertising in local print publications still draws a positive ROI. I focus on specific, "trendy" (I hate to use that word) publications focusing on arts, culture, and local events. Generally these are far less expensive than advertising in the main newspaper, and the readers are more in line with the type of customers I want to attract (people searching for quality over price). The price was well under $1000.
▌███▐ Fresh Roasted Hosting: Pennsylvania web hosting since January 2012!
▌███▐ Xen PV VPS :: Custom Dedicated Servers :: Co-Location :: Shared
▌███▐ Harrisburg PA :: Dunmore PA :: Dallas TX :: Los Angeles CA
There is some brilliant advice here. For all its worth and I am sorry if it has already been said but I find video marketing or youtube marketing very helpful. Just post a tutorial on youtube with a link at the end to your website. I have got good traffic from it. Youtube has hundreds of millions of users, it would be seriously dumb to not tap into it.
While this technique may work better for companies that already have an established client base, you might consider it for yourself for the future.
USPS.com offers a service where you can print and mail full-color postcards with custom text and even a logo for just $.79c a piece. Imagine what kind of an effect it would have on your clients if you sent them the postcards thanking them for their businesses and asking them for referrals (or you can simply imply that you have an affiliate program where you pay $X/referral).
In this day and age, a postcard from a hosting company would be considered unusual but very, very classy. It just associates your company with professionalism and the fact that you really care about your clients and are willing to go above and beyond to make sure they are happy.
I love this method, makes a company looks professional.