Can an optout link be included in a scheduled reminder?
Provide them with a link back to a webform with checksum plus activity id if necessary so the existing Activity is loaded, and set the webform submission to change the status of the Activity to something that is excluded in the Scheduled Reminder.

(NB I am trying to get some unanswered questions answered as that is currently the 'weakest' aspect of our Beta civicrm stackexchange according to these [stats][1])