My humble opinion is that you are over analyzing this. Unfortunately, no solution is going to be 100% fool proof. Even captchas are not 100% reliable and hacks for them are publicly available. Even the sound based captchas have been broken into. The answers posted by others here are good options to start with. Start with them, and see how many bad requests get filtered out. If they filter out 90% of the bad requests, you just need to analyze and learn the patterns of the rest of the 10% and put in point solutions (IP filtering, throttling etc) which will fix those.
You can't prevent 100% of bad requests hitting your server 100% of the time. You just do your best to prevent them and have a plan to mitigate the damage.