@decay, hard to answer that i am gonna give you tips.
Take a dedi you'll have your own ip if you're blacklisted it will not harm your provider or at least not his mail service (some third party now blacklist entire networks when one single ip is considered as spam source).
Create SPF record in your domain zone.
Filter your mailing lists, if some people should not receive the mails dont send them the mails otherwise they will probably send an abuse to your provider.
MX rescue is a record you set in the domain dns zone.
It is the MX used your main server fails to send your mails.
Comments
Your domain registrar most likely offers this for free.
@decay, hard to answer that i am gonna give you tips.
Take a dedi you'll have your own ip if you're blacklisted it will not harm your provider or at least not his mail service (some third party now blacklist entire networks when one single ip is considered as spam source).
Create SPF record in your domain zone.
Filter your mailing lists, if some people should not receive the mails dont send them the mails otherwise they will probably send an abuse to your provider.
MX rescue is a record you set in the domain dns zone.
It is the MX used your main server fails to send your mails.
@decay If you're sending in bursts you might want to look at mandrill.com