Do the directories use a captcha? I know some people think captchas are annoying. I think people that want more back links would be willing to fill a captcha in. It blocked 99.9% of my spam whenever I use it on forms.
I personally like:
reCAPTCHA: Stop Spam, Read Books
If you know php or know someone who can integrate it in for ya.