If you start stripping affiliate IDs, I'll just write a redirector and link to that, or link to an existing redirector. Are you going to ban all of bit.ly? Or t.co? or letter.obscure_tld from your website?
It wasn't that hard to pick out URLs that were not user facing (that a bookmark let would never see)
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.