Ask HN: Solutions for sending large volume of emails in a social network

Assume you are Foursquare and you want to send e-mail notifications to your users when * someone adds you as friend or confirms your request * someone comments on your check-in * monthly newsletters etc. Therefore if you reach more than a few thousands of users, mail deliverability will become a problem. I'm looking for solutions to my startup with almost the same use cases. My criteria are deliverability (sent messages are not considered as spam), low cost (per mail). First solutions that came to my mind are: * local mail server setup * Amazon Simple Email Service (SES) * other solutions? Any experiences on this issue?