I know this is an old post,
However we are doing this by actually exporting the tables from SQL which gives you the NewsLetterSubscriptionGuid for the user. Then you can include the string for removal in the email. Either encrypt the link (better, but not so simple) or just include the actual string.
We use ecampaign (others are available and cheaper for smaller campaigns. But we have used it for years. Works a treat.
As typing this I just had an IDEA!
IMPROVEMENT TO EXPORT
Add the capability to export the NewsLetterSubscriptionGuid , storeID and signup time. Should be easy to add functionality to export to CSV. This would be an AWESOME feature.