That's a bummer that the bi-directional communication does not help with your filtering.
However, asking the user to add your address to their address book may help.
You may also consider dividing your list up with multiple sender/receiver pairs. Subscriber A would get the email from your Sender A, and reply to her. Subscriber B would get the email from your Sender B, and reply to him. At least total counts from Sender A would be lower than a single Sender.
I'm assuming you are also using SPF (v1 and v2) and DKIM correctly.
If I was in the newsletter sending game, I suppose I would try Constant Contact and Mail Chimp and others like that, to see what they do (they probably all recommend the privacy eroding features, but you might learn some tricks).