Don't know if it would work, really, but most linkbots seem to be a one-shot job, posting, then dying. How about an 'introductions' forum that you can only see if you have <1 (ie 0) posts, and is the only forum you can see. After posting there, it disappears for you, and you can then post in the rest of the boards. You can always read the main forums, so Google etc. can spider.
One-post bots would never get past this, and if the posts were cleared every day/week/month/whatever to free up space and reduce the risk of them posting in the main boards later. Good idea/bad idea? Just plain stupid?
EDIT: Changed some stupid typos.