Zoho is pretty cheap and not bad. They also own Zeptomail [1] that is meant for transactional emails, also cheap and you can even buy credits in advance. Haven't tried it yet though.
So I did the reasonable thing and signed up for Zoho. It's cheap and I don't have to worry about having a zombie spam server because I misconfigured something.