There are a couple of reasons why your contacts may be experiencing difficulties unsubscribing.
It could be because the contact has been sent an email to an old email address they used to use, and their IT team has set things up to redirect email for this address to their current address.
For example, let's say my current email address is:
However, all my old email addresses still work, which are:
The other reason this can happen is that the email was sent to an alias. For example, I get email redirected to my account which has been sent to:
...and a whole lot more!