I think I've figured out a little more on this one.
When editing a mailing list there a property called "Friendly Unsubscribe". When that is set, then the #UnsubscribeLink# in the message will use the correct href to unsubscribe and the text will be whatever is in that property.
It's when the Friendly Unsubscribe property is left blank that we see the issue - the correct href is used but the text of the link is incorrect (it uses the format from SM15 and earlier).