When I first started, a few years ago now, I put a free ad in the local Parish Magazine......that netted me 60 odd customers in the first couple of months....I still get the odd call ...despite not being in it for over a year now....good result for nothing eh !
Maybe, being in a local christian based rag...it lends an air of respectability to it (if if it's good enough for the Vicar....etc ) I don't know, but it worked !