If the workload is made to be very large, say 30 seconds on a recent desktop, it could fall back to a captcha for slower devices. At least people visiting with fast computers could be spared the captcha.
That's a very good idea, coupled with what other people have suggested (Increase the time on the fly for devices/IPs making repeated or spammy looking requests) I could see this working.
