For those considering listings in a directory:
How did you find the directory? If it's listed on some SEO site's list - it's probably also on the SE's list. Also see bulls-eye effect below.
Do they come up for your terms? If they are nowhere to be found in any of the terms you are going for - why list with them?
Do have contact info? What if you need to contact them? Many trash directories have no contact forms or info of any kind.
What's the whois info look like? Is it private? "Real companies" seldom use private registration (ducking).
The bull's-eye effect: Do you notice any of the following:
"Part of the hyperlink Network"
"This site SEO'd By hyperlink"
"Web Design by hyperlink"
If you find they use the terms "search engine benefit", "links", "SEO", "linking", Google PR, or any other type of SEO language on their site, think twice. They are probably now or will soon be on the radar of SE's.
Investigate their domain/hosting: Use a tool like whois.webhosting.info (not affiliated) and lookup their domain/IP to see if they have a "network" of like sites. These sites can often disappear from SE's in one fell swoop.
Navigate the site and use their search: If the site has slow response times it could very well be done "on-the-cheap". Is the site easy to navigate? Is the search facility at least reasonably accurate?
Are the pages cached by SE's? If they are, yet do not come up for any terms this could be for several reasons - none of them being good (unless it's a brand-new page/category).
What's the fee?: When considering a listing or advertising in a directory - add up the costs. If it's a one-time fee and is reasonable, you normally cannot go wrong if it meets the criteria discussed. When you get into annual or monthly fees, compare to what PPC is costing for your terms this site/directory comes up for. Weigh that out and divide by how many other listings in your prospective category and try to figure out the number of clicks you can expect and what they will actually be costing you compared to other major PPC avenues.
Don't be surprised if site owners either do not give you stats (many reasons for this), track them, or if they do offer them they will probably be inflated. Rely on your own judgment and not theirs!
I'm sure people can add to the above, but at least it's a start..