Otherwise, the spammer will be able to run his/her own URL shortener service in a 5USD/month VPS and be able to show a spammy link to the users and a regular-looking link for the crawler.
BTW: a "crawler" implemented with Mechanical Turk workers would be a little bit harder to detect, but would also have its downsides.
How are these challenges exactly? Just set the user-agent and enable cookies. Done.
"...also operate from many distinct and perpetually changing IP addresses."
Okay. Change the IP it operates on every few days.