First I would suggest you get rid of one click unsubscribe and replace it with a preference center page so it won't happen again.

To answer your question though, I have struggled with this exact issue and the only success I've found is to undo all the opt out boxes in both SFDC and Pardot at the same time. Save them within seconds of each other and sync both to make sure it stuck.

Otherwise, you could have the recipient fill in any form on your site, but that's not the easiest for your Prospect.