One thing you could do is make users have a TOS they agree to at the time of signup for the newsletter as well as logging their IP, then prior to sending them their first newsletter, auto reject any IPs that do not match to the email provided (this would likely mean gmail, yahoo & hotmail addresses will always invalidate, but by doing this you make sure they are who they say they are rather than putting a phony email) or have a phone number required and call users before adding them into the list.
For sending the newsletter, you can give each user a unique uid when the newletters are sent to be part of the subject title so that if they do report you as spam after agreeing to receive your newsletter, you can a) determine quickly who reported you to get rid of them from the list immediately, b) seek any damages against them they might have cost you via their negligence as you have the TOS they agreed to for this provision (making sure you include something in the TOS about reporting you for spam rather than opting out by clicking your opt out link will result in your ability to seek such damanges should any occur, including damaging your site and business reputation through their purposeful activity or negligence of following proper opt out protocol). You could even seek a lawyer for the best type of legal contract to make up for the TOS.
Note: After writing this, though, I'm not certain you are asking about users reporting you for spamming or instead about your newsletters accidentally getting tagged by email filters as spam. If this is the issue instead, then one way to get your email less likely to be tagged as spam by a filter would be to ensure the sender's email is the one that is actually sending the newsletter and that the email is hard-coded in the script sending out the email. Many mailing list programs don't really explicitly list the email sender and this causes filters to tag them as spam. What email program are you using to send messages? If Mailman, I would highly suggest changing to something you can configure like Dada Mail instead.