There are a couple of possibilities as to why your contacts may be experiencing difficulties unsubscribing.
It could be because the user has been sent an email to an old email address they used to use and the IT team has set up to redirect mail to 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!!