Make a crawler that follows your redirects. If it hits an affiliate page, you can presume (with some likelihood) that it's a spam link.
If you put in intermediate redirects that the crawler wouldn't pick up, there's a chance your targets won't either and you'll lose customers.
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.