All this is nice and well, but how would one build an "unsubscribe" link into a newsletter system without a GET request changing the state of the resource (i.e. deleting the email address from the active recipients table by just clicking a link)?
Would this be the exception to the rule or is this problem totally unrelated to REST?
These are guidelines and not unbreakable rules. I think it's fine to have unsubscribe link change the state of the resource. [And personally, I would only flag the user for not sending emails, not delete his email altogether.]
It depends on where the link is. If it's in a web page and the user's browser supported any valid method in forms, you could use a form with method="DELETE" and action="uri for user's subscription", with a submit button styled to look like a link. For browsers that don't support the DELETE method in forms, you can add a hidden input _method=DELETE which is the semi-standard workaround for incomplete browser support. (Your service has to look for _method when it gets a POST and react accordingly.)
If the link is in an email, a form probably won't work. Email clients are still worse than browsers when it comes to styling buttons to look like links. In that case, you can use a real link, but add the _method=DELETE to the url parameters. You service can then look for _method on GET requests too. But it's bad and hacky to change a GET into a DELETE, so you really should just use the link to display a web page, then delete with a DELETE or POST from there. That's what most unsubscribe links in emails do anyway.
In my opinion, you should not initiate a removal from an email. In part due to this. Instead you give the recipient a link to a web page where you have a form that sends either a POST or DELETE to the application.
"Should not" used in the rfc2119 definition. There are always exceptions.
Would this be the exception to the rule or is this problem totally unrelated to REST?
BTW: I'm not debating, I really wanna know.