I think your best bet is Amazon ses. In my recent testing, all mail always go through - unless the recipient marks it thus.

It's damn cheap too, like almost free for low volumes.

I think Amazon uses this for their workmail also and has become pretty strict at policing abuse.

I am only speaking for gmail though, so ymmv for hotmail et al which I haven't checked.