We worked out what was going on here.
The unsubscribe token was being copied and pasted into the email messages. It was copied from a source that included some HTML code behind.
As per the manual, the token should be typed in as plain text, there cannot be any html code in the token it's self. Best way to do this is to type it in, rather than copy and paste.