My general philosophy for businesses is that it's ideal for them to be findable in as many places as possible. Also, if the directory allows links to your site, leveraging as many inbound links as possible is also ideal.
So, where free directories are concerned, I think people should attempt to be listed in as many as possible, with the caveat that you want to avoid those that may spam you, and definitely not do any reciprocal linking, as others in the thread adeptly recommended.
So, for free, I don't consider quality to be of any sort of major factor. The real factor with free directories would be the ROI story -- you might sign up for listings in thousands of these, but at some point, the lower-quality ones will have less traffic that would convert to you, and it might not make sense for you to register with all of the lesser ones since your time and work doing that might not pay for itself after a certain threshold.
As for Paid, just as others here have mentioned, you need to assess whether the paid listing is returning more than the cost to you. Also, some free directories give more prominent placement and extra promotion/contact information for paid listings with them.
Summary of my philosophy:
- For Free, get as many as possible without expending so much time registering that you won't make up for the time investment;
- For Paid, choose those which are most likely to convert well for you, test them if possible with short duration campaigns, and adjust your spend by reducing or deleting campaigns with low-conversion directories and increasing or remaining stable with nicely-converting directories.