We had a similar problem.
We send out e-mail newsletters to our subscribers so to ensure delivery I went ahead and set up a private postfix relay!
The VPS service we use is
Cheap VPS Hosting at VPSLink and it's been rock-solid for 18 months and only costs about $7pm.
All our outgoing mail from Zimbra / our intranet database / newsletter system is routed through that, not our ISPs relay, plus we have total control of the DNS.
Hope this helps
Cheers, B