When outputting {email_url} without anchor tags, the output is correct. Same for {profile_url}
So no problem there. It is the actual url of a link that is messed up.
I tried using a new default template, but problem persists.
I can also tell you this behaviour only occurs in the newsletters itself. Not in the subscription mails etc, nor in any other wordpress generated email.