Ask HN: How to stop bots/spammers in their tracks on an entry form?

We're trying to come up with a solution to a major spam and bot issue we've been having. Basically, we have an entry form for people to fill out asking for basic information (name, email, address, etc. --sometimes we ask for just email).

Our forms are posted on thousands of websites and domains, and so we've started to see incoming spam and bots executing the forms, submitting fake information.

So far we've employed these things to stop them:

1) IP is blocked after 3 submissions from the same IP.

2) We check the http referrer to ensure its coming from the expected page. If is not, we kill the entry.

3) If an email has already been entered once, the system won't record it again.

4) We've added captcha, but most of our customers don't want to use it since it reduces form submissions.

Our form is submitted via AJAX request. Currently the bots are submitting the request to the AJAX file and the HTTP_REFERRER is coming from the expected page, and no information is coming across that would suggest they are using a proxy.

I could be incorrect, but it appears as though they have a macro set up that is rotating through IPs using a new one each time, and automatically filling in our form fields, and submitting them, exactly as a human would do.

As of late we've seen these bots submitting our forms thousands of times, all using the same type of address (like @yahoo or @hotmail) but the submissions are all coming from different IP addresses, so we can't detect and block them. After entering some of these IP's into an IP checker, it looks like a majority of them are coming from proxy servers.

One idea we've come up with to try and stop the spam is that when a user types into one of the fields, javascript invokes a cookie. When they go to submit the form, if the cookie isn't found, we drop the entry. Would this work?

Any suggestions/ideas on how to best combat this would be greatly appreciated!