I have a report of a user reporting a similar problem when using the unsubscribe tag, this issue is under investigation. Can your problem be related to the same thing?
On our last newsletter I had five people unsubscribe. Three of these are personally known to ne and have informed me that they did not unsubscribe but received an email saying they had.
That's really really weird... Are you sure they did not press the Unsubscribe link on your message? In the MaxBulk Mailer preferences, are you sure your MLM URL is correct?