Was das Einverständnis des Nutzers betrifft: dieses ist tatsächlich die Voraussetzung, wenn legal Daten erhoben, gespeichert oder sogar weitergegeben werden sollen (siehe § 4 BDSG).
Dass du mir widersprichst habe ich schon vermutet. Aber ehrlich gesagt hätte ich von dir aufgrund deiner juristischen Kenntnisse eine bessere Argumentation erwartet.
1. in der von dir verlinkten Norm steht - sogar noch vor der möglichen Einwilligung - dass die Verwendung von Daten unter anderem dann erlaubt ist, wenn ein Gesetz dies erlaubt.
2. bei reiner BDSG-Anwendung sehe ich absolut keine Probleme, sowas ohne Einwilligung zu machen. Selbst wenn, kann man von einer konkludenten EInwilligung ausgehen
3. Das Problem ist, dass das BDSG hier nicht viel zu melden hat, da das strengere TMG Vorrang hat. Aber wie gesagt. Auch nach dem TMG gehe ich davon aus, dass zumindest bei den meisten Newslettern keine Einwilligung nötig ist.