"Paid or free" is the wrong question to ask. A paid link must be marked as "nofollow", so you definitely won't get any googlejuice from it. On the other hand, as I said, a free link from a directory is unlikely to be worth anything much in the eyes of a search engine. So the only value to directory links is their potential to direct real people to your website. And whether a directory is paid or free doesn't necessarily have any bearing on that. There are, I have no doubt, some directories out there that have a lot of traffic (at least in particular niches) and don't charge anything for submission, and others that charge for entries and can't back that up with traffic.
If you're going down the route of directory submission, the only questions to consider is whether you are likely to get a lot of people for whom your site would be of interest seeing the link to your site, and how much control you have over the link in terms of placement, presentation, text and context.