When an email bounces, do you flag it in your system so that you don't continue to send emails to it? Not speaking from personal experience, but I've read that certain major webmail companies will penalize your server if you keep trying to deliver mail to an invalid account within a certain time frame.

You seem to have everything else covered, that's the only thing that comes to mind.