flicker - 3:28 pm on Sep 12, 2006 (gmt 0)

If they're abusing the nofollow tags for the benefit of their own PageRank, you could always try informing Google. That's explicitly *not* how Google wants that tag used, but I'm guessing it would have to be a really clear PR manipulation for them to actually act on it (plus you'd need to be lucky and catch the right quality-control guy on the right day.)

If you paid them for a link and the amount you paid them is not worth it if Google won't recognize the link, then you could try asking them for your money back. If it's a free directory then why worry about it, you may still get a few referrals from them.