As of the moment, paid directories are good. Compared to free directories, paid directories maintains quality submissions, which are manually edited by human editors. Their are also lots of quality free directories though, but most quality directories are those that has paid submissions.
The Yellow page is a search directory just so you know. They charge upwards of $400 per MONTH for their premium listing. Do people use them - Heck ya they do. A Good listing in a Good business directory can actually do much better for a business in Google than even a very expensive web site the business owner may have. (I can prove that by the way). It matters not how someone gets to your business - Just that they get there. I have a solution designed for the small guys however. Ask me. Links are well - Links (no meaningful CONTENT). Google wants to see Content and a lot of it which is informative, full rich html type content, photos, and more to do anything with it. Directories are ideal for that such as Manta, Linkedin are also Directories and they are FREE. The best directories have no other links in the page which features YOUR business (very few of those) which helps pull the optimum PRV ranking over to your site, and are easy to search, easy to add/manage your listing, and are coded well (even fewer are)...