The biggest problem I see with any of these "3rd party promotions" is that once it leaves your house, you have no control. Regardless of how "legitimate" your intentions are, it only takes one of your "3rd party partners" to sell off the list they get from you.
Example: I sign up for these "3rd party promotions" when I install your software. You sell your list to, say, 5 companies. Each of those sell it to 5 companies, etc. Before long I'm getting dozens or more "useful 3rd party promotional emails" per day. Naturally, I visit your website to unsubscribe from these promotions, but then what? Now I have to unsubscibe from every list I receive. It's nearly impossible to keep up with that. Not to mention that one cannot tell which were referred by you, and which were harvested (i.e. do not reply, lest you be spammed to death).
Here's my suggestions to all of the companies like yours"
1. List ALL of your 3rd party partners and ensure that they list EVERY organization that they sell their lists to.
2. Maintain strict standards of your partners to ensure that their methods are as ethical as yours.
3. Use a trickle-down unsubscribe process whereby you pass along unsubscribe information to all your partners, and they to theirs, etc. Also, ensure that these requests are honored.
4. Use a closed-loop system and ensure all of your partners do the same. It makes no difference that your company follows some minimum guidelines. You should strive to exceed those guidelines.
And my suggestion to all email recipients:
1. Use disposable email addresses for ALL newsletter and forum correspondence. This makes it easy to "cut the ties" if things get out of control. You can always sign back up for those that you wish to receive again with another address.
2. Use some sort of filter or classification software. I use POPFile (GNU, available at sourceforge) which is very good at classifying email and learning according to how I've classified other email. It also inserts a [tag] in the subject line if you want. I then use the message rules in my email client to move these messages to different folders.
3. Report genuine spam to the originating ISP. For those novices, you can paste the header into SpamCop and it will tell you the email address to use.
I think for the the general Internet public, RSS would be a good step. Even newletters that I subscribe to don't necessarily interest me. With RSS I can choose which of those I actually want to read. Of course, this will cut down on the advertising revenue, meaning that some newsletters will choose not to use RSS.