Comment by mrweasel

What I'd be concerned with is that if you have never sent anything to these users, they might have forgotten where and when they gave you their email address and simply mark your message as spam.

We've trained users to not use "unsubscribe" because some spammers once used that to verify addresses, or they may simply click "Spam" because they forgot who you are and think you got their address illegitimately. Gmail also doesn't make unsubscribe as visible as "Spam", making flagging the easier option. So now Gmail will see some percentage of users manually flagging you as a spammer, tainting your sender. This is why I'd switch the newsletter to a new domain or at least a new sender address. That does mean preparing that new sender, give it a bit of time to mature and send a few emails to Gmail accounts you control and ensure that they are not flagged as spam.

Probably also test with a list of Gmail account you control and check if you're tagged as spam and fix that, before doing the big push.